leetcode 282 - Expression Add Operators

https://leetcode.com/problems/expression-add-operators/
http://zxi.mytechroad.com/blog/searching/leetcode-282-expression-add-operators/

Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators ‘+’, ‘-‘, or ‘*’ between the digits of num so that the resultant expression evaluates to the target value.

Example 1:

Input: num = “123”, target = 6
Output: [“123”,”1+2+3”]
Example 2:

Input: num = “232”, target = 8
Output: [“23+2”,”2+32”]
Example 3:

Input: num = “105”, target = 5
Output: [“1*0+5”,”10-5”]
Example 4:

Input: num = “00”, target = 0
Output: [“0*0”,”0+0”,”0-0”]
Example 5:

Input: num = “3456237490”, target = 9191
Output: []

Constraints:

1 <= num.length <= 10
num consists of only digits.
-231 <= target <= 231 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
vector<string> all_results;

void helper(string &num, int target, //input
int i, string &expr, long result, long prev, long cur, char op) { //state
if (i == (int)num.size()) {
if (op == '*') {
result = result - prev + prev * cur;
} else {
result = result + cur;
}

if (result == target)
all_results.push_back(expr);
return;
}

char c = num[i];

if (!(expr.size() && cur == 0)) {
expr.push_back(c);
int neg = cur < 0 ? -1 : 1;
helper(num, target, i+1, expr, result, prev, (abs(cur)*10+(c-'0'))*neg, op);
expr.pop_back();
}

if (op == '*') {
result = result - prev + prev * cur;
prev = prev * cur;
} else {
result = result + cur;
prev = cur;
}

cur = c - '0';

if (i > 0) {
expr.push_back('+');
expr.push_back(c);
helper(num, target, i+1, expr, result, prev, cur, '+');
expr.pop_back();
expr.pop_back();

expr.push_back('-');
expr.push_back(c);
helper(num, target, i+1, expr, result, prev, -cur, '-');
expr.pop_back();
expr.pop_back();

expr.push_back('*');
expr.push_back(c);
helper(num, target, i+1, expr, result, prev, cur, '*');
expr.pop_back();
expr.pop_back();
}
}

vector<string> addOperators(string num, int target) {
string expr;
helper(num, target, 0, expr, 0, 0, 0, '+');
return all_results;
}
};

leetcode 65 - Valid Number

https://leetcode.com/problems/valid-number/

A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An ‘e’ or ‘E’, followed by an integer.
A decimal number can be split up into these components (in order):

(Optional) A sign character (either ‘+’ or ‘-‘).
One of the following formats:
At least one digit, followed by a dot ‘.’.
At least one digit, followed by a dot ‘.’, followed by at least one digit.
A dot ‘.’, followed by at least one digit.
An integer can be split up into these components (in order):

(Optional) A sign character (either ‘+’ or ‘-‘).
At least one digit.
For example, all the following are valid numbers: [“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”], while the following are not valid numbers: [“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = “0”
Output: true
Example 2:

Input: s = “e”
Output: false
Example 3:

Input: s = “.”
Output: false
Example 4:

Input: s = “.1”
Output: true

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus ‘+’, minus ‘-‘, or dot ‘.’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
/* -123.456e+789 */
bool isNumber(string s) {
bool digit_seen = false, dot_seen = false, e_seen = false;

int n = s.size();
for (int i = 0; i < n; i++) {
char c = s[i];

if (c == '-' || c == '+') {
if (i != 0 && s[i-1] != 'e' && s[i-1] != 'E')
return false;
} else if (c == '.') {
if (dot_seen || e_seen)
return false;
dot_seen = true;
} else if (c == 'e' || c == 'E') {
if (e_seen || !digit_seen) return false;
e_seen = true;
digit_seen = false;
} else if (c >= '0' && c <= '9') {
digit_seen = true;
} else {
return false;
}
}

return digit_seen;
}
};

leetcode 987 - Vertical Order Traversal of a Binary Tree

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.
Example 2:

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.
Example 3:

Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int most_left(TreeNode *root, int col) {
if (!root)
return col;

if (root->left)
col = min(col, most_left(root->left, col-1));
if (root->right)
col = min(col, most_left(root->right, col+1));

return col;
}

int most_right(TreeNode *root, int col) {
if (!root)
return col;

if (root->right)
col = max(col, most_right(root->right, col+1));
if (root->left)
col = max(col, most_right(root->left, col-1));

return col;
}

vector<vector<pair<int,int>>> result;

void dfs(TreeNode *root, int row, int col) {
if (!root) return;

result[col].push_back({row, root->val});
dfs(root->left, row+1, col-1);
dfs(root->right, row+1, col+1);
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
int left = most_left(root, 0);
int right = most_right(root, 0);
int width = right - left + 1;

result.resize(width);
dfs(root, 0, abs(left));

vector<vector<int>> ans;
for (auto &row : result) {
if (row.empty()) continue;

sort(row.begin(), row.end());

ans.push_back({});
for (auto &p : row)
ans.back().push_back(p.second);
}

return ans;
}
};

//global sorting
class Solution {
public:
vector<vector<int>> nums_tuple; //{col, row, val}

void helper(TreeNode *root, int row, int col) {
if (!root) return;

nums_tuple.push_back({col, row, root->val});
helper(root->left, row+1, col-1);
helper(root->right, row+1, col+1);
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<vector<int>> result;

helper(root, 0, 0);

sort(nums_tuple.begin(), nums_tuple.end());

for (int i = 0; i < nums_tuple.size(); i++) {
int col = nums_tuple[i][0];
int val = nums_tuple[i][2];

if (i == 0 || col != nums_tuple[i-1][0])
result.push_back({val});
else
result.back().push_back(val);
}

return result;
}
};

leetcode 454 - 4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums[l] == 0

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:

  1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
    Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Constraints:

n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//general solution to handle K sum 
class Solution {
public:
unordered_map<int, int> count;

void add_to_hash(vector<vector<int>> &nums_list, int sum, int row) {
if (row >= nums_list.size()/2) {
count[sum]++;
return;
}

for (int col = 0; col < nums_list[row].size(); col++)
add_to_hash(nums_list, sum + nums_list[row][col], row+1);
}

int get_ans(vector<vector<int>> &nums_list, int sum, int row) {
if (row == nums_list.size())
return count[-sum];

int ans = 0;
for (int col = 0; col < nums_list[row].size(); col++)
ans += get_ans(nums_list, sum + nums_list[row][col], row+1);

return ans;
}

int kSumCount(vector<vector<int>> &nums_list) {
add_to_hash(nums_list, 0, 0);

return get_ans(nums_list, 0, nums_list.size()/2);
}

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
vector<vector<int>> nums_list;

nums_list.push_back(nums1);
nums_list.push_back(nums2);
nums_list.push_back(nums3);
nums_list.push_back(nums4);

return kSumCount(nums_list);
}
};

leetcode 378 - Kth Smallest Element in a Sorted Matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
Example 2:

Input: matrix = [[-5]], k = 1
Output: -5

Constraints:

n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
1 <= k <= n2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
#define It vector<int>::iterator

struct Comp {
bool operator()(const pair<It, It> &p1, const pair<It, It> &p2) {
return *(p1.first) > *(p2.first);
}
};

int kthSmallest(vector<vector<int>>& matrix, int k) {
priority_queue<pair<It, It>, vector<pair<It, It>>, Comp> pq;

for (auto &row : matrix)
pq.push({row.begin(), row.end()});

while (--k > 0) {
auto p = pq.top(); pq.pop();

if (++p.first != p.second)
pq.push({p.first, p.second});
}

return *pq.top().first;
}
};

leetcode 655 - Print Binary Tree

https://leetcode.com/problems/print-binary-tree/

Print a binary tree in an m*n 2D string array following these rules:

The row number m should be equal to the height of the given binary tree.
The column number n should always be an odd number.
The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
Each unused space should contain an empty string “”.
Print the subtrees following the same rules.
Example 1:
Input:
1
/
2
Output:
[[“”, “1”, “”],
[“2”, “”, “”]]
Example 2:
Input:
1
/
2 3

4
Output:
[[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“”, “”, “4”, “”, “”, “”, “”]]
Example 3:
Input:
1
/
2 5
/
3
/
4
Output:

[[“”, “”, “”, “”, “”, “”, “”, “1”, “”, “”, “”, “”, “”, “”, “”]
[“”, “”, “”, “2”, “”, “”, “”, “”, “”, “”, “”, “5”, “”, “”, “”]
[“”, “3”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]
[“4”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]]
Note: The height of binary tree is in the range of [1, 10].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
vector<vector<string>> printTree(TreeNode* root) {
int depth = get_depth(root);
int width = (1 << depth) - 1;

vector<vector<string>> result(depth, vector<string>(width, ""));

print(root, result, 0, 0, width-1);

return result;
}

int get_depth(TreeNode *root) {
if (!root) return 0;

return max(get_depth(root->left), get_depth(root->right)) + 1;
}

void print(TreeNode *root, vector<vector<string>> &result, int d, int l, int r) {
if (!root) return;

int m = l + (r-l) / 2;

result[d][m] = to_string(root->val);
print(root->left, result, d+1, l, m-1);
print(root->right, result, d+1, m+1, r);
}
};

leetcode 393 - UTF-8 Validation

https://leetcode.com/problems/utf-8-validation/

Given an integer array data representing the data, return whether it is a valid UTF-8 encoding.

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For a 1-byte character, the first bit is a 0, followed by its Unicode code.
For an n-bytes character, the first n bits are all one’s, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.
This is how the UTF-8 encoding would work:

Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
——————–+———————————————
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:

Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one’s and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that’s correct.
But the second continuation byte does not start with 10, so it is invalid.

Constraints:

1 <= data.length <= 2 * 10^4
0 <= data[i] <= 255

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
bool validUtf8(vector<int>& data) {
int n = data.size();
int bytes_to_process = 0;

for (int i = 0; i < n; i++) {
if (bytes_to_process == 0) {
int bits = get_leading_bits(data[i]);
if (bits == 1 || bits > 4) return false;

if (bits)
bytes_to_process = bits - 1;
} else {
if (get_leading_bits(data[i]) != 1)
return false;
bytes_to_process--;
}
}

return bytes_to_process == 0;
}

int get_leading_bits(int num) {
int bit = 0;

for (int i = 7; i >= 0; i--) {
if ((num & (1 << i)) == 0)
break;
bit++;
}

return bit;
}
};

leetcode 399 - Evaluate Division

https://leetcode.com/problems/evaluate-division/

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

Input: equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
Example 2:

Input: equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:

Input: equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj consist of lower case English letters and digits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_map<string, vector<pair<string, double>>> graph;

int n = equations.size();
for (int i = 0; i < n; i++) {
string &a = equations[i][0];
string &b = equations[i][1];

graph[a].push_back({b, 1.0/values[i]});
graph[b].push_back({a, values[i]});
}

vector<double> result;

for (auto &query : queries) {
if (graph.count(query[0]) == 0 || graph.count(query[1]) == 0)
result.push_back(-1.0);
else
result.push_back(bfs(graph, query[1], query[0]));
}

return result;
}

double bfs(unordered_map<string, vector<pair<string, double>>> &graph, string &a, string &b) {
queue<pair<string, double>> q;
unordered_set<string> seen;

q.push({a, 1.0});
seen.insert(a);

while (!q.empty()) {
int n = q.size();

for (int i = 0; i < n; i++) {
auto p = q.front(); q.pop();
if (p.first == b)
return p.second;

auto &edges = graph[p.first];
for (auto &e : edges) {
if (seen.count(e.first)) continue;

q.push({e.first, p.second * e.second});
seen.insert(e.first);
}
}
}

return -1.0;
}
};

leetcode 427 - Construct Quad Tree

https://leetcode.com/problems/construct-quad-tree/

Given a n * n matrix grid of 0’s and 1’s only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

val: True if the node represents a grid of 1’s or False if the node represents a grid of 0’s.
isLeaf: True if the node is leaf node on the tree or False if the node has the four children.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e all 1’s or all 0’s) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

Example 3:

Input: grid = [[1,1],[1,1]]
Output: [[1,1]]
Example 4:

Input: grid = [[0]]
Output: [[1,0]]
Example 5:

Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output: [[0,1],[1,1],[1,0],[1,0],[1,1]]

Constraints:

n == grid.length == grid[i].length
n == 2^x where 0 <= x <= 6
Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
// Definition for a QuadTree node.
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;

Node() {
val = false;
isLeaf = false;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}

Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}

Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
*/

class Solution {
public:
Node* construct(vector<vector<int>>& grid) {
return recursive(grid, 0, 0, grid.size()-1, grid[0].size()-1);
}

Node *recursive(vector<vector<int>> &grid, int x1, int y1, int x2, int y2) {
if (all_same(grid, x1, y1, x2, y2))
return new Node(grid[x1][y1], true);

Node *parent = new Node(1, false);
parent->topLeft = recursive(grid, x1, y1, (x1+x2)/2, (y1+y2)/2);
parent->topRight = recursive(grid, x1, (y1+y2)/2+1, (x1+x2)/2, y2);
parent->bottomLeft = recursive(grid, (x1+x2)/2+1, y1, x2, (y1+y2)/2);
parent->bottomRight = recursive(grid, (x1+x2)/2+1, (y1+y2)/2+1, x2, y2);
return parent;
}

bool all_same(vector<vector<int>> &grid, int x1, int y1, int x2, int y2) {
int rows = x2 - x1 + 1;
int cols = y2 - y1 + 1;

for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[x1+r][y1+c] != grid[x1][y1])
return false;
}
}

return true;
}
};

leetcode 966 - Vowel Spellchecker

https://leetcode.com/problems/vowel-spellchecker/

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
Example: wordlist = [“yellow”], query = “YellOw”: correct = “yellow”
Example: wordlist = [“Yellow”], query = “yellow”: correct = “Yellow”
Example: wordlist = [“yellow”], query = “yellow”: correct = “yellow”
Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
Example: wordlist = [“YellOw”], query = “yollow”: correct = “YellOw”
Example: wordlist = [“YellOw”], query = “yeellow”: correct = “” (no match)
Example: wordlist = [“YellOw”], query = “yllw”: correct = “” (no match)
In addition, the spell checker operates under the following precedence rules:

When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
When the query matches a word up to capitlization, you should return the first such match in the wordlist.
When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
If the query has no matches in the wordlist, you should return the empty string.
Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = [“KiTe”,”kite”,”hare”,”Hare”], queries = [“kite”,”Kite”,”KiTe”,”Hare”,”HARE”,”Hear”,”hear”,”keti”,”keet”,”keto”]
Output: [“kite”,”KiTe”,”KiTe”,”Hare”,”hare”,””,””,”KiTe”,””,”KiTe”]
Example 2:

Input: wordlist = [“yellow”], queries = [“YellOw”]
Output: [“yellow”]

Constraints:

1 <= wordlist.length, queries.length <= 5000
1 <= wordlist[i].length, queries[i].length <= 7
wordlist[i] and queries[i] consist only of only English letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
unordered_set<string> words;
unordered_map<string, vector<int>> words_lowercase;
unordered_map<string, vector<int>> words_vowel;

int n = wordlist.size();
for (int i = 0; i < n; i++) {
words.insert(wordlist[i]);
words_lowercase[get_key_lowercase(wordlist[i])].push_back(i);
words_vowel[get_key_vowel(wordlist[i])].push_back(i);
}

vector<string> result;

for (auto &query : queries) {
if (words.count(query)) {
result.push_back(query);
continue;
}

string key = get_key_lowercase(query);
if (words_lowercase.count(key)) {
int idx = words_lowercase[key].front();
result.push_back(wordlist[idx]);
continue;
}

key = get_key_vowel(query);
if (words_vowel.count(key)) {
int idx = words_vowel[key].front();
result.push_back(wordlist[idx]);
continue;
}

result.push_back("");
}

return result;
}

string get_key_lowercase(string word) {
for (int i = 0; i < word.size(); i++) {
if (word[i] >= 'A' && word[i] <= 'Z')
word[i] = word[i] - 'A' + 'a';
}

return word;
}

string get_key_vowel(string word) {
word = get_key_lowercase(word);
string vowel = "aeiou";
for (int i = 0; i < word.size(); i++) {
for (char v : vowel) {
if (word[i] == v) {
word[i] = '*';
break;
}
}
}

return word;
}
};