## Sunday, July 24, 2016

### LeetCode 97 - Interleaving String

http://buttercola.blogspot.com/2014/09/leetcode-interleaving-string.html
Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = `"aabcc"`,
s2 = `"dbbca"`,

When s3 = `"aadbbcbcac"`, return true.
When s3 = `"aadbbbaccc"`, return false.
X. DP
https://robinliu.gitbooks.io/algorithms/content/shuang_xu_lie_xing.html

state: `f[i][j]`: 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否组成 s3 的前 i+j 个字符
fucntion: `f[i][j] = (f[i-1][j] && s1[i-1] == s3[i+j-1]) || (f[i][j-1] && s2[j-1] == s3[i+j-1])`

https://discuss.leetcode.com/topic/7728/dp-solution-in-java
We can use DP to solve this problem. So the steps are:

• Define boolean dp[str1.length() + 1][str2.length() + 1], where dp[ i ][ j ] : means whether str1.charAt(0) to str1.charAt(i) and str2.charAt(0) to str2.charAt(j) could construct the string str3, from 0 to i + j.
• Transit function:
• dp[i][j]  = str3.charAt(i + j) == str1.charAt(i) && dp[ i - 1][j] ||
• str3.charAt(i + j) == str2.charAt(j) && dp[i][j - 1]
• Initial State
• dp[0][0] = true;
• dp[0][j] = str3.charAt(j) == str2.charAt(j)
• dp[i][0] = str3.charAt(i) == str1.charAt(i)
• Final state dp[str1.length()][str2.length()].
`    ``public` `boolean` `isInterleave(String s1, String s2, String s3) {`
`        ``if` `(s1 == ``null` `|| s2 == ``null` `|| s3 == ``null``) {`
`            ``return` `false``;`
`        ``}`
`        `
`        ``if` `(s1.length() == ``0` `&& s2.length() == ``0` `&& s3.length() == ``0``) {`
`            ``return` `true``;`
`        ``}`
`        `
`        ``if` `(s1.length() + s2.length() != s3.length()) {`
`            ``return` `false``;`
`        ``}`
`        `
`        ``boolean``[][] dp = ``new` `boolean``[s1.length() + ``1``][s2.length() + ``1``];`
`        ``dp[``0``][``0``] = ``true``;`
`        `
`        ``for` `(``int` `i = ``1``; i <= s2.length(); i++) {`
`            ``if` `(s2.charAt(i - ``1``) == s3.charAt(i - ``1``)) {`
`                ``dp[``0``][i] = ``true``;`
`            ``} ``else` `break``;`
`        ``}`
`        `
`        ``for` `(``int` `i = ``1``; i <= s1.length(); i++) {`
`            ``if` `(s1.charAt(i - ``1``) == s3.charAt(i - ``1``)) {`
`                ``dp[i][``0``] = ``true``;`
`            ``} ``else` `break``;`
`        ``}`
`        `
`        ``for` `(``int` `i = ``1``; i <= s1.length(); i++) {`
`            ``for` `(``int` `j = ``1``; j <= s2.length(); j++) {`
`                ``if` `(s3.charAt(i + j - ``1``) == s1.charAt(i - ``1``)) {`
`                    ``dp[i][j] = dp[i - ``1``][j];`
`                ``}`
`                `
`                ``if` `(s3.charAt(i + j - ``1``) == s2.charAt(j - ``1``)) {`
`                    ``dp[i][j] = dp[i][j] || dp[i][j - ``1``];`
`                ``}`
`            ``}`
`        ``}`
`        `
`        ``return` `dp[s1.length()][s2.length()];`
`    ``}`
```    public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}

boolean [][] interleaved = new boolean[s1.length() + 1][s2.length() + 1];
interleaved[0][0] = true;

for (int i = 1; i <= s1.length(); i++) {
if(s3.charAt(i - 1) == s1.charAt(i - 1) && interleaved[i - 1][0])
interleaved[i][0] = true;
}

for (int j = 1; j <= s2.length(); j++) {
if(s3.charAt(j - 1) == s2.charAt(j - 1) && interleaved[0][j - 1])
interleaved[0][j] = true;
}

for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if(((s3.charAt(i + j - 1) == s1.charAt(i - 1) && interleaved[i - 1][j]))
|| ((s3.charAt(i + j - 1)) == s2.charAt(j - 1) && interleaved[i][j - 1]))
interleaved[i][j] = true;
}
}

return interleaved[s1.length()][s2.length()];
}
```

public boolean isInterleave(String s1, String s2, String s3) {
if (s1==null || s2==null || s3==null) return false;
if (s1.length()==0 && s2.length()==0 && s3.length()==0) return true;
if ((s1.length()+s2.length())!=s3.length()) return false;
boolean valid[] = new boolean[s2.length()+1];
valid[0] = false;
for (int j=1; j<=s2.length(); j++){
if (s2.charAt(j-1)==s3.charAt(j-1)) valid[j]=true;
}
for (int i=1; i<=s1.length(); i++){
if (s1.charAt(i-1)==s3.charAt(i-1)) valid[0]=true;
for (int j=1; j<=s2.length(); j++){
valid[j] = (valid[j] && s1.charAt(i-1)==s3.charAt(i+j-1)) ||
(valid[j-1] && s2.charAt(j-1)==s3.charAt(i+j-1));
}
}
return valid[s2.length()];
}

``````public static boolean isInterleaveOptz(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length()) return false;

boolean[] optimal = new boolean[s2.length() + 1];    //dp optimal
optimal[0] = true;
for (int j = 0; j < s2.length(); j++) { //check no s1 char is selected, if s2 could equals to s3
if (optimal[j] && s2.charAt(j) == s3.charAt(j)) optimal[j + 1] = true;
}

for (int i = 0; i < s1.length(); i++) { //check select i-th char in s1
if (optimal[0] && s1.charAt(i) == s3.charAt(i)) optimal[0] = true;    //no char in s2 is selected
else optimal[0] = false;
for (int j = 0; j < s2.length(); j++) {  //select j-th char
if ((s1.charAt(i) == s3.charAt(i + j + 1) && optimal[j + 1]) ||
s2.charAt(j) == s3.charAt(i + j + 1) && optimal[j]) {
optimal[j + 1] = true;
} else optimal[j + 1] = false;
}
}
return optimal[s2.length()];
}``````

``````public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
String maxWord = s1.length() > s2.length() ? s1 : s2;
String minWord = s1.length() > s2.length() ? s2 : s1;
boolean[]dp = new boolean[minWord.length() + 1];
dp[0] = true;

for (int i = 0; i < minWord.length(); i++) {
if (minWord.charAt(i) == s3.charAt(i) && dp[i] == true) {
dp[i + 1] = true;
}
}
for (int i = 1; i <= maxWord.length(); i++) {
dp[0] = dp[0] && maxWord.charAt(i - 1) == s3.charAt(i - 1);
for (int j = 1; j <= minWord.length(); j++) {
dp[j] = s3.charAt(i + j - 1) == maxWord.charAt(i - 1) && dp[j] == true || s3.charAt(i + j - 1) == minWord.charAt(j - 1) && dp[j - 1] == true;
//此处不能再用if判断, 因为dp[j]已经有值 必须要赋值true/false
}
}

return dp[minWord.length()];
}``````

public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null) return false;
if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) return true;
if ((s1.length() + s2.length()) != s3.length()) return false;
String shorterString, longerString;
if (s1.length() < s2.length()) {
shorterString = s1;
longerString = s2;
} else {
shorterString = s2;
longerString = s1;
}
boolean[] valid = new boolean[shorterString.length() + 1];
valid[0] = true;
for (int i = 1; i <= shorterString.length(); i++) {
if (shorterString.charAt(i-1)==s3.charAt(i-1)) valid[i]=true;
}
for (int i = 1; i <= longerString.length(); i++) {
for (int j = 1; j <= shorterString.length(); j++) {
valid[j] = (valid[j] && longerString.charAt(i-1)==s3.charAt(i+j-1)) ||
(valid[j-1] && shorterString.charAt(j-1)==s3.charAt(i+j-1));
}
}
return valid[shorterString.length()];
}

X. Recursive version
1. public boolean isInterleave(String s1, String s2, String s3) {
2.       if(s1.length() == 0){
3.         if( s2.equals(s3))return true;
4.         else return false;
5.       }else if(s2.length() == 0){
6.         if(s1.equals(s3)) return true;
7.         else return false;
8.       }
9.       if(s3.charAt(0) == s1.charAt(0) && s3.charAt(0) != s2.charAt(0)){
10.         return isInterleave(s1.substring(1), s2, s3.substring(1));
11.       }else if(s3.charAt(0) == s2.charAt(0) && s3.charAt(0) != s1.charAt(0)){
12.         return isInterleave(s1, s2.substring(1), s3.substring(1));
13.       }else if(s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0)){
14.         return isInterleave(s1.substring(1), s2, s3.substring(1)) || isInterleave(s1, s2.substring(1), s3.substring(1));
15.       }else{
16.         return false;
17.       }
18.   }

If we expand the two strings s1 and s2 into a chessboard, then this problem can be transferred into a path seeking problem from the top-left corner to the bottom-right corner. The key is, each cell (y, x) in the board corresponds to an interval between y-th character in s1 and x-th character in s2. And adjacent cells are connected with like a grid. A BFS can then be efficiently performed to find the path.
Better to illustrate with an example here:
Say s1 = "aab" and s2 = "abc". s3 = "aaabcb". Then the board looks like
``````o--a--o--b--o--c--o
|     |     |     |
a     a     a     a
|     |     |     |
o--a--o--b--o--c--o
|     |     |     |
a     a     a     a
|     |     |     |
o--a--o--b--o--c--o
|     |     |     |
b     b     b     b
|     |     |     |
o--a--o--b--o--c--o
``````
Each "o" is a cell in the board. We start from the top-left corner, and try to move right or down. If the next char in s3 matches the edge connecting the next cell, then we're able to move. When we hit the bottom-right corner, this means s3 can be represented by interleaving s1 and s2. One possible path for this example is indicated with "x"es below:
``````x--a--x--b--o--c--o
|     |     |     |
a     a     a     a
|     |     |     |
o--a--x--b--o--c--o
|     |     |     |
a     a     a     a
|     |     |     |
o--a--x--b--x--c--x
|     |     |     |
b     b     b     b
|     |     |     |
o--a--o--b--o--c--x
``````
Note if we concatenate the chars on the edges we went along, it's exactly s3. And we went through all the chars in s1 and s2, in order, exactly once.
Therefore if we view this board as a graph, such path finding problem is trivial with BFS. I use an `unordered_map` to store the visited nodes, which makes the code look a bit complicated. But a `vector` should be enough to do the job.
Although the worse case timeis also O(mn), typically it doesn't require us to go through every node to find a path. Therefore it's faster than regular DP than average.
``````    public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) return false;
boolean[][] visited = new boolean[s1.length() + 1][s2.length() + 1];
queue.offer(new int[]{0, 0});
while (!queue.isEmpty()) {
int[] p = queue.poll();
if (visited[p[0]][p[1]]) continue;
if (p[0] == s1.length() && p[1] == s2.length()) return true;

if (p[0] < s1.length() && s1.charAt(p[0]) == s3.charAt(p[0] + p[1]))
queue.offer(new int[]{p[0] + 1, p[1]});
if (p[1] < s2.length() && s2.charAt(p[1]) == s3.charAt(p[0] + p[1]))
queue.offer(new int[]{p[0], p[1] + 1});
visited[p[0]][p[1]] = true;
}
return false;
}``````

``````struct MyPoint {
int y, x;
bool operator==(const MyPoint &p) const {
return p.y == y && p.x == x;
}
};
namespace std {
template <>
struct hash<MyPoint> {
size_t operator () (const MyPoint &f) const {
return (std::hash<int>()(f.x) << 1) ^ std::hash<int>()(f.y);
}
};
}

class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;

queue<MyPoint> q;
unordered_set<MyPoint> visited;
bool isSuccessful = false;
int i = 0;

q.push(MyPoint { 0, 0 });
q.push(MyPoint { -1, -1 });
while (!(1 == q.size() && -1 == q.front().x)) {
auto p = q.front();
q.pop();
if (p.y == s1.size() && p.x == s2.size()) {
return true;
}
if (-1 == p.y) {
q.push(p);
i++;
continue;
}
if (visited.find(p) != visited.end()) { continue; }
visited.insert(p);

if (p.y < s1.size()) { // down
if (s1[p.y] == s3[i]) { q.push(MyPoint { p.y + 1, p.x }); }
}
if (p.x < s2.size()) { // right
if (s2[p.x] == s3[i]) { q.push(MyPoint { p.y, p.x + 1 }); }
}
}
return false;
}
};``````
Imagine a grid, which x-axis and y-axis are s1 and s2, matching s3 is the same as
finding a path from (0,0) to (len1, len2). It actually becomes a
BFS on grid. Since we don't need exact paths, a HashSet of
coordinates is used to eliminate duplicated paths.
``````    public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length(),
len2 = s2.length(),
len3 = s3.length();
if (len1 + len2 != len3) return false;
int matched = 0;
queue.offer(0);
Set<Integer> set = new HashSet<>();
while (queue.size() > 0 && matched < len3) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int p1 = queue.peek() / len3,
p2 = queue.peek() % len3;
queue.poll();
if (p1 < len1 && s1.charAt(p1) == s3.charAt(matched)) {
int key = (p1 + 1) * len3 + p2;
if (!set.contains(key)) {
queue.offer(key);
}
}
if (p2 < len2 && s2.charAt(p2) == s3.charAt(matched)) {
int key = p1 * len3 + (p2 + 1);
if (!set.contains(key)) {
queue.offer(key);
}
}
}
matched++;
}
return queue.size() > 0 && matched == len3;
}``````
https://discuss.leetcode.com/topic/19900/python-dp-solutions-o-m-n-o-n-space-bfs-dfs/2
``````def isInterleave(self, s1, s2, s3):
r, c, l= len(s1), len(s2), len(s3)
if r+c != l:
return False
queue, visited = [(0, 0)], set((0, 0))
while queue:
x, y = queue.pop(0)
if x+y == l:
return True
if x+1 <= r and s1[x] == s3[x+y] and (x+1, y) not in visited: