leetCode Question: Word Pattern

Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Analysis:

This problem is not hard but needs you be more careful with all the conditions:

  • The length of the words in str and chars in pattern may be different
  • The char to word is a bijection, which means it is a one-to-one mapping.
  • Don't forget to handle the last word when you split the str.

Here for the bijection mapping, I just used two maps, one save (word, char), and the other to save (char, word).

Code (C++):

class Solution {
public:
bool wordPattern(string pattern, string str) {
map<char, string> mp1;
map<string, char> mp2;
string tmp = "";
int j = 0;
for (int i=0;i<=str.size();i++){
if (j == pattern.size()){ return false; }
if (str[i]==' ' || i == str.size()){
if (mp1.find(pattern[j]) == mp1.end() && mp2.find(tmp) == mp2.end()){
mp1[pattern[j]] = tmp;
mp2[tmp] = pattern[j++];
}else{
if (mp1[pattern[j]] == tmp && mp2[tmp] == pattern[j]){ j++; }
else{ return false; }
}
tmp = "";
}else{
tmp += str[i];
}
}
if (j != pattern.size()){return false;}
return true;
}
};

Code (Python):

class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
mp1 = {}
mp2 = {}
words = str.split(' ')
if len(words)!=len(pattern):
return False
for word, ch in zip(words, pattern):
if word not in mp1 and ch not in mp2:
mp1[word] = ch
mp2[ch] = word
elif mp1.get(word) == ch and mp2.get(ch) == word:
pass
else:
return False
return True

leetCode Question: Game of Life

Game of Life

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.

Follow up:
Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Analysis:

At the first glance, the solution is pretty straightforward without considering the "in-place" requirement. For each element in the array, we could compute the accumulated sum of its 8 neightbours. Check out the rules required in the question, set the corresponding value in a new array. Done.

Now let's handle the "in-place". Firstly, let's take a look at the rules and all possible values for each element:

  • If cell $x_t$ in time $t$ is alive ($x_t = 1$):
    • If sum of neighbour $s{x_t}$ = 2 or 3, then $x{t+1} = 1$
    • If $s{x_t} = 0, 1, 4, 5,6, 7, 8$, then $x{t+1} = 0$
  • If cell $x_t = 0$,
    • If $s{x_t} = 3$, then $x{t+1} = 1$
    • otherwise, $x_{t+1} = 0$

Now considering the case that, everytime after we compute one cell $xt$, and then write the value $x{t+1}$ back to the position, we lost the value in time $t$ so that it's impossible to compute the next cell in the same state.

Here note that the matrix doesn't have to be binary (0 or 1 only). What if we write the sum $s_t$ back to the position instead of the value of next state? Therefore, to obtain the next state, we just need to reset the values according to the rules. It looks like a good idea, however, how can we keep the original state of each cell at the same time is still a problem. So we have to figure out a way to "compute" the $x_t$ from $s_t$.

Note that, when cell is dead, there is only one case it will be alive in the next state. In other words, when $xt = 0$, unless $s_t = 3$, we could set the write 0 back to the array, since $x_t = x{t+1} = 0$. For the special case, we could simply write a negative value to distinguish the alive cells. To compute the current sum, we no longer have only binary values in the array, but also integers. But it is still easy to tell whether it was a 1 or 0, before we set the sum to it, by comparing the value with 0. Finally we want:

  • No matter the value in current cell indicates the state (alive or dead), or sum of its neighbour, it must be alive if it's greater than zero, and dead less than or equal to zero.

So when the cell is alive, the state value is 1. The sum value are positive integers except one special case 0. The good thing is the rule in the probelm treat sum 0 and 1 the same when state value is 1. So we could just set 0 to 1 since it will not effect the next state, while keep our criteria well.

Now with the criteria (comparison with 0) and two special cases (x=0, s=3, and x=1, s=0 ), we could compute and set the cells one by one in place, finally just reset the value according to the rules will result in the next state.

Code (C++):

class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int r = board.size();
if (r==0){return;}
int c = board[0].size();
for (int i=0;i<r;++i){
for (int j=0; j<c;++j){
int tmp = 0;
if (i-1 >=0 && j-1>=0){ tmp += (board[i-1][j-1] >0);}
if (i-1 >=0){ tmp += (board[i-1][j] >0);}
if (i-1 >=0 && j+1<c){ tmp += (board[i-1][j+1] >0);}
if (j+1<c){ tmp += (board[i][j+1] >0);}
if (i+1 <r && j+1<c){ tmp += (board[i+1][j+1] >0);}
if (i+1 <r ){ tmp += (board[i+1][j] >0);}
if (i+1 <r && j-1>=0){ tmp += (board[i+1][j-1] >0);}
if ( j-1>=0 ) { tmp += (board[i][j-1] >0);}
//cout << "tmp[" << i << "][" << j << "]=" << tmp << endl;
if (board[i][j]==0){
if (tmp == 3){
board[i][j] = -3;
}
}else{
if (tmp == 0){
board[i][j] = 1;
}else{
board[i][j] = tmp;
}
}
}
}
// for (int i=0;i<r;++i){
// for (int j=0; j<c;++j){
// cout << board[i][j] << ", ";
// }
// cout << endl;
// }
for (int i=0;i<r;++i){
for (int j=0; j<c;++j){
if (board[i][j] == -3){
board[i][j] = 1;
}else if (board[i][j] == 2 || board[i][j] == 3){
board[i][j] = 1;
}else{
board[i][j] = 0;
}
}
}
}
};

Code (Python):

class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
r = len(board)
if r == 0:
return
c = len(board[0])
for i in range(r):
for j in range(c):
tmp = 0
if i-1 >= 0 and j-1 >= 0:
tmp += (board[i-1][j-1] > 0)
if i-1 >=0:
tmp += (board[i-1][j] > 0)
if i-1 >=0 and j+1 < c:
tmp += (board[i-1][j+1] > 0)
if j+1 < c:
tmp += (board[i][j+1] > 0)
if i+1 < r and j+1 < c:
tmp += (board[i+1][j+1] > 0)
if j-1 >= 0 :
tmp += (board[i][j-1] > 0)
if i+1 < r :
tmp += (board[i+1][j] > 0)
if i+1 < r and j-1 >= 0 :
tmp += (board[i+1][j-1] > 0)
#print "tmp[", i, "][", j, "]=", tmp
if board[i][j] == 0:
if tmp == 3:
board[i][j] = -3
else:
if tmp == 0:
board[i][j] = 1
else:
board[i][j] = tmp
for i in range(r):
for j in range(c):
if board[i][j] == -3:
board[i][j] = 1
elif board[i][j] == 2 or board[i][j] == 3:
board[i][j] = 1
else:
board[i][j] = 0

leetCode Question: Expression Add Operators

Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:
"123", 6 -> ["1+2+3", "123"]
"232", 8 -> ["23+2", "2+32"]
"105", 5 -> ["10+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0
0"]
"3456237490", 9191 -> []

Analysis:

Usually when we met the word "all possibilities", it means we have to search all the "paths" and check each possible solution. In other words, search (remember DFS and BFS ?) is a good way to handle this kind of problem.

So in this problem, we found the problem contains two phases:

  1. Split the numbers in the string and add operators +, - or *
  2. calculate the value of the string expression, e.g., 1+2×3

The 1st phase is that we could apply the DFS (Depth First Search). In the DFS search, for every possible positions between two numbers in the string, we has four options:

  • add operator +
  • add operator
  • add operator
  • don't add operator, go to next char

In the code level, we will have a search function which is the main part of DFS, which can be birefly summarized as follows:

search(current string, pervious number, current value){
//check string length
if current string is empty:
if current value == target //check current value and target value
save result // store result
else // current string is not empty, keep search
for i = 1 to string length // we will add operator in i-th position
convert the number from string[0 to i]
//add operator and keep searching
search (string[i:end], equation + number, previous number, current val)
search (string[i:end], equation - number, pervious number, current val)
search (string[i:end], equation * number, previous number, current val)
} // when i ==string length, we don't add operater, treat the string as a single number
}
}

The 2nd phase, a traditional way to solve it is to use the stack, to calculate the infix expression (or convert infix to postfix expression then use stack to compute the value). However, as the code shown below (C++, slow version), it exceeded the time limit for long strings. Why? Because the final value of the expression, is always computed after the whole expression is formulated, but for similar expressions (child nodes with same parent) we compute the same part muliple times. E.g., 1+2×3+4+5, and 1+2×3+45, we don't have to compute the value 1+2×3 twice.

But how can we "memorize" the values computed below and keep the operator precedence at the same time? Let's take a example, say we have expression:

1+2×3=1+6=7

In our DFS procedure, firstly we have expression
1+2=3

which can be viewed as:
1+2=3

previous value+current number=current value

Then we have met operator × and current value 3, it looks like but a wrong expression:

previous value 3×current number 3=current value 9

Because multiplication operator has higher precedence than addition operator, in this expression, we should firstly do ×, then do +. So, we have:

1+2=3
32+23=1+6=7

which can be generalized into:

( previous value previous number )+( previous number×current number )=current value 

Once you have the idea of the above expression, the + and operator will be much more easier to handle.

Code (C++):

class Solution {
public:
void search(string num, string equation, long last, long cur, int& target,vector<string>& res){
if (num.size() == 0){
if (target == cur){ res.push_back(equation);}
}else{
for (int i=1;i<= num.size(); i++){
string n = num.substr(0,i);
if (n.size()> 1 && n[0] == '0'){return;}
long nl = stoll (n);
if (equation.size() > 0){
search(num.substr(i), equation + "+" + n, nl, cur + nl, target, res);
search(num.substr(i), equation + "-" + n, -nl, cur - nl, target, res);
search(num.substr(i), equation + "*" + n, last * nl, (cur - last)+(last * nl), target, res);
}else{
search(num.substr(i), n, nl, nl, target, res);
}
}
}
}
vector<string> addOperators(string num, int target) {
vector<string> res;
search(num,"",0,0, target, res);
return res;
}
};

Code (Python):

class Solution(object):
def search(self, num, eq, last, cur, target, res):
if len(num) == 0:
if cur == target:
res.append(eq)
else:
for i in range(1, len(num)+1):
n = num[0:i]
if len(n) > 1 and n[0]=='0':
return
if len(eq)>0:
self.search(num[i:], eq + '+' + n, int(n), cur + int(n), target, res)
self.search(num[i:], eq + '-' + n, -int(n), cur - int(n), target, res)
self.search(num[i:], eq + '*' + n, last*int(n), (cur-last) + (last * int(n)), target, res)
else:
self.search(num[i:], n, int(n), int(n), target, res)
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
res = []
self.search(num, "", 0, 0, target, res)
return res

Code (C++, slow version):

class Solution {
public:
long calc(string eq){
stack<long> nums;
stack<char> ops;
string tmp = "";
for (int i=0;i<eq.size();i++){
if (eq[i]=='+' || eq[i]=='-' || eq[i]=='*'){
nums.push(stoll(tmp));
tmp = "";
while (!ops.empty() && ops.top()=='*'){
ops.pop();
long tmp1 = nums.top();
nums.pop();
long tmp2 = nums.top();
nums.pop();
nums.push(tmp1*tmp2);
}
ops.push(eq[i]);
}else{
tmp += eq[i];
}
}
//last number
nums.push(stoll(tmp));
while (!ops.empty()){
long tmp1 = nums.top();
nums.pop();
long tmp2 = nums.top();
nums.pop();
if (ops.top() == '+'){ nums.push(tmp2 + tmp1);}
else if (ops.top()=='-'){nums.push(tmp2 - tmp1);}
else {nums.push(tmp2*tmp1);}
ops.pop();
}
return nums.top();
}
void search(string num, string equation, int& target,vector<string>& res){
if (num.size()==1){
equation = equation + num;
if (target == calc(equation)){
res.push_back(equation);
}
}else{
for (int i=1;i<num.size(); i++){
search(num.substr(i), equation + num.substr(0,i) + "+", target, res);
search(num.substr(i), equation + num.substr(0,i) + "-", target, res);
search(num.substr(i), equation + num.substr(0,i) + "*", target, res);
}
}
}
vector<string> addOperators(string num, int target) {
vector<string> res;
search(num,"", target, res);
return res;
}
};