## Sunday, December 24, 2017

### LeetCode OJ - Sentence Similarity II

Problem:

Solution:

The code is a little difficult to read just by itself, here is the high level idea.

First, we map each word appeared in the pair array into a single number. That allow us the build a graph based on just numbers. We build a two way map for this.

Next, we build a graph based on the numbers. The graph is represented as adjacency list.

Then we assign an unique number to each connected component, the connected component is found by BFS. Each word is mapped to its connected component number.

Finally we compare the words. If they are identical, then it is good, otherwise if they have the same connected component number, we are still good.

Otherwise it is not good and fail the similarity test.

Analysis:

The implementation avoids string comparison as much as possible for speed. The BFS algorithm is the fastest possible to find connected components in linear time. The check is also fast.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/sentence-similarity-ii

#include "LEET_SENTENCE_SIMILARITY_II.h"
#include <map>
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <queue>

using namespace std;

namespace _LEET_SENTENCE_SIMILARITY_II
{
class Solution {
public:
bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs)
{
if (words1.size() != words2.size())
{
return false;
}

map<string, int> numbers;
map<int, string> strings;
map<string, int> canon;
map<int, set<int>> graph;
for (auto&& p : pairs)
{
int n1;
auto probe1 = numbers.find(p.first);
if (probe1 == numbers.end())
{
n1 = numbers.size();
numbers.insert(make_pair(p.first, n1));
strings.insert(make_pair(n1, p.first));
}
else
{
n1 = probe1->second;
}
int n2;
auto probe2 = numbers.find(p.second);
if (probe2 == numbers.end())
{
n2 = numbers.size();
numbers.insert(make_pair(p.second, n2));
strings.insert(make_pair(n2, p.second));
}
else
{
n2 = probe2->second;
}
auto probe3 = graph.find(n1);
if (probe3 == graph.end())
{
graph.insert(make_pair(n1, set<int>()));
}
graph[n1].insert(n2);
auto probe4 = graph.find(n2);
if (probe4 == graph.end())
{
graph.insert(make_pair(n2, set<int>()));
}
graph[n2].insert(n1);
}

vector<bool> enqueued;
enqueued.resize(numbers.size());
for (int i = 0; i < numbers.size(); i++)
{
enqueued[i] = false;
}

int cc = 0;
queue<int> bfs;
for (int i = 0; i < numbers.size(); i++)
{
if (!enqueued[i])
{
enqueued[i] = true;
bfs.push(i);
while (!bfs.empty())
{
int v = bfs.front();
bfs.pop();
canon.insert(make_pair(strings[v], cc));
for (auto&& neighbor : graph[v])
{
if (!enqueued[neighbor])
{
enqueued[neighbor] = true;
bfs.push(neighbor);
}
}
}
cc++;
}
}

for (int i = 0; i < words1.size(); i++)
{
if (words1[i] == words2[i])
{
continue;
}
auto probe1 = canon.find(words1[i]);
if (probe1 == canon.end())
{
return false;
}
auto probe2 = canon.find(words2[i]);
if (probe2 == canon.end())
{
return false;
}
if (probe1->second != probe2->second)
{
return false;
}
}

return true;
}
};
};

using namespace _LEET_SENTENCE_SIMILARITY_II;

int LEET_SENTENCE_SIMILARITY_II()
{
Solution s;
vector<string> words1;
words1.push_back("great");
words1.push_back("acting");
words1.push_back("skills");
vector<string> words2;
words2.push_back("fine");
words2.push_back("drama");
words2.push_back("talent");
vector<pair<string, string>> pairs;
pairs.push_back(make_pair("great", "good"));
pairs.push_back(make_pair("fine", "good"));
pairs.push_back(make_pair("acting", "drama"));
pairs.push_back(make_pair("skills", "talent"));
cout << s.areSentencesSimilar(words1, words2, pairs) << endl;
return 0;
}

Problem:

Solution:

## Thursday, December 7, 2017

### LeetCode OJ - Sentence Similarity

Problem:

Solution:

Because the relationship is not transitive, I cannot map them both into a single canonical representation. Therefore I simply iterate the map and try to map both and see if one and be mapped to another.

I could have index the pairs to avoid the inner loop, but turn out the mapping could be one to many, which means I need an unordered_map to and unordered_set. It is doable, I am just lazy since this work good enough.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/sentence-similarity

#include "LEET_SENTENCE_SIMILARITY.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SENTENCE_SIMILARITY
{
class Solution
{
public:
bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs)
{
if (words1.size() != words2.size())
{
return false;
}

for (int i = 0; i < words1.size(); i++)
{
string& word1 = words1[i];
string& word2 = words2[i];
if (word1 == word2)
{
continue;
}
bool found = false;
for (int j = 0; j < pairs.size(); j++)
{
if (pairs[j].first == word1 && pairs[j].second == word2)
{
found = true;
break;
}
if (pairs[j].first == word2 && pairs[j].second == word1)
{
found = true;
break;
}
}
if (!found)
{
return false;
}
}
return true;
}
};
};

using namespace _LEET_SENTENCE_SIMILARITY;

int LEET_SENTENCE_SIMILARITY()
{
Solution s;
vector<string> words1;
words1.push_back("great");
words1.push_back("acting");
words1.push_back("skills");
vector<string> words2;
words2.push_back("fine");
words2.push_back("drama");
words2.push_back("talent");
vector<pair<string, string>> pairs;
pairs.push_back(make_pair("great", "fine"));
pairs.push_back(make_pair("drama", "acting"));
pairs.push_back(make_pair("skills", "talent"));
cout << s.areSentencesSimilar(words1, words2, pairs) << endl;
return 0;
}

## Wednesday, November 29, 2017

### LeetCode OJ - Split Linked List in Parts

Problem:

Solution:

It is simple math, for the first $n \mod k$ lists, there is one more item, otherwise we have $\left\lfloor \frac{n}{k} \right\rfloor$ items.

Code:

#include "stdafx.h"

#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

{
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* root, int k)
{
int size = 0;
ListNode* cur = root;
ListNode* prev = nullptr;
while (cur != NULL)
{
size++;
cur = cur->next;
}
int part_size = size / k;
int part_excess = size % k;
vector<ListNode*> result;
result.resize(k);
cur = root;
for (int i = 0; i < k; i++)
{
result[i] = cur;
for (int j = 0; j < part_size; j++)
{
if (cur != nullptr)
{
prev = cur;
cur = cur->next;
}
}
if (part_excess > 0)
{
if (cur != nullptr)
{
prev = cur;
cur = cur->next;
}
part_excess = part_excess - 1;
}
if (prev != nullptr)
{
prev->next = nullptr;
}
}
return result;
}
};
};

{
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
Solution s;
vector<ListNode*> result = s.splitListToParts(&a, 3);
for (ListNode* r : result)
{
ListNode* u = r;
while (u != nullptr)
{
cout << u->val << " -> ";
u = u->next;
}
cout << "nullptr" << endl;
}
return 0;
}

## Saturday, October 14, 2017

### LeetCode OJ - Binary Number with Alternating Bits

Problem:

Solution:

This one is easy, there are only so many numbers with alternating bits, just list them all.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-number-with-alternating-bits

#include "LEET_BINARY_NUMBER_WITH_ALTERNATING_BITS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_BINARY_NUMBER_WITH_ALTERNATING_BITS
{
class Solution
{
public:
bool hasAlternatingBits(int n)
{
switch (n)
{
case 0x00:
case 0x01:
case 0x02:
case 0x05:
case 0x0A:
case 0x15:
case 0x2A:
case 0x55:
case 0xAA:
case 0x155:
case 0x2AA:
case 0x555:
case 0xAAA:
case 0x1555:
case 0x2AAA:
case 0x5555:
case 0xAAAA:
case 0x15555:
case 0x2AAAA:
case 0x55555:
case 0xAAAAA:
case 0x155555:
case 0x2AAAAA:
case 0x555555:
case 0xAAAAAA:
case 0x1555555:
case 0x2AAAAAA:
case 0x5555555:
case 0xAAAAAAA:
case 0x15555555:
case 0x2AAAAAAA:
case 0x55555555:
case 0xAAAAAAAA:
return true;
default:
return false;
}
}
};
};

using namespace _LEET_BINARY_NUMBER_WITH_ALTERNATING_BITS;

int LEET_BINARY_NUMBER_WITH_ALTERNATING_BITS()
{
Solution solution;
cout << solution.hasAlternatingBits(5) << endl;
return 0;
}

### LeetCode OJ - Valid Parenthesis String

Problem:

Analysis:

Without the star character, the problem can be solved simply by maintaining a counter represents the amount of open parenthesis. We require that it never go below zero and it reach zero at the end. With star, we do not know what to do with the counter.

Solution:

What we could do, instead of maintaining the counter value, maintain an upper bound and a lower bound on the possible values of the counter. We need to make sure the upper bound never goes below zero, if it does, the string cannot possibly be valid. We need to make sure the lower bound never goes below zero, and the range contains 0 at the end of the string.

Maintaining the bounds take only $O(1)$ time per character, so overall it is an $O(n)$ algorithm.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/valid-parenthesis-string

#include "LEET_VALID_PARENTHESIS_STRING.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_VALID_PARENTHESIS_STRING
{
class Solution
{
public:
bool checkValidString(string s)
{
int u = 0;
int l = 0;
for (int i = 0; i < s.length(); i++)
{
char c = s[i];
switch (c)
{
case '(':
u++;
l++;
break;
case ')':
u--;
l--;
if (u < 0) { return false; }
if (l < 0) { l = 0; }
break;
case '*':
u++;
l--;
if (l < 0) { l = 0; }
break;
}
}
return u >= 0 && l <= 0;
}
};
};

using namespace _LEET_VALID_PARENTHESIS_STRING;

int LEET_VALID_PARENTHESIS_STRING()
{
Solution solution;
cout << solution.checkValidString("()") << endl;
cout << solution.checkValidString("(*)") << endl;
cout << solution.checkValidString("((*)") << endl;
return 0;
}

### LeetCode OJ - Max Area of Island

Problem:

Solution:

We simply do a BFS on the graph and return the best tree size. As an optimization, instead of using a separate set to mark if the node is visited, we set the grid entry to be -1 instead.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/max-area-of-island

#include "LEET_MAX_AREA_OF_ISLAND.h"
#include <iostream>
#include <queue>
#include <map>
#include <string>

using namespace std;

namespace _LEET_MAX_AREA_OF_ISLAND
{
class Solution
{
public:
int maxAreaOfIsland(vector<vector<int>>& grid)
{
if (grid.size() == 0)
{
return 0;
}
int height = grid.size();
int width = grid[0].size();
int max_size = 0;
for (int row = 0; row < height; row++)
{
if (grid[row].size() != width)
{
throw 1;
}
for (int col = 0; col < width; col++)
{
if (grid[row][col] == 1)
{
int size = 0;
queue<pair<int, int>> bfs;
bfs.push(make_pair(row, col));
grid[row][col] = -1;
while (bfs.size() > 0)
{
auto current = bfs.front();
int current_row = current.first;
int current_col = current.second;

size++;
bfs.pop();
if (current_row + 1 < height && grid[current_row + 1][current_col] == 1)
{
bfs.push(make_pair(current_row + 1, current_col));
grid[current_row + 1][current_col] = -1;
}
if (current_col + 1 < width && grid[current_row][current_col + 1] == 1)
{
bfs.push(make_pair(current_row, current_col + 1));
grid[current_row][current_col + 1] = -1;
}
if (current_row - 1 >= 0 && grid[current_row - 1][current_col] == 1)
{
bfs.push(make_pair(current_row - 1, current_col));
grid[current_row - 1][current_col] = -1;
}
if (current_col - 1 >= 0 && grid[current_row][current_col - 1] == 1)
{
bfs.push(make_pair(current_row, current_col - 1));
grid[current_row][current_col - 1] = -1;
}
}
max_size = max(size, max_size);
}
}
}
return max_size;
}
};
};

using namespace _LEET_MAX_AREA_OF_ISLAND;

int LEET_MAX_AREA_OF_ISLAND()
{
Solution solution;
int row0[] = { 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 };
int row1[] = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0 };
int row2[] = { 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 };
int row3[] = { 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0 };
int row4[] = { 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0 };
int row5[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 };
int row6[] = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0 };
int row7[] = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 };
vector<vector<int>> grid;
grid.push_back(vector<int>(row0, row0 + _countof(row0)));
grid.push_back(vector<int>(row1, row1 + _countof(row1)));
grid.push_back(vector<int>(row2, row2 + _countof(row2)));
grid.push_back(vector<int>(row3, row3 + _countof(row3)));
grid.push_back(vector<int>(row4, row4 + _countof(row4)));
grid.push_back(vector<int>(row5, row5 + _countof(row5)));
grid.push_back(vector<int>(row6, row6 + _countof(row6)));
grid.push_back(vector<int>(row7, row7 + _countof(row7)));
cout << solution.maxAreaOfIsland(grid) << endl;
return 0;
}