-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInterleavingString.cpp
More file actions
40 lines (35 loc) · 1.08 KB
/
InterleavingString.cpp
File metadata and controls
40 lines (35 loc) · 1.08 KB
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
/**
Given s1, s2, s3, 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.
[Analysis]
Classical dp, consider 5 cases
*/
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (s3.size() != m +n) return false;
vector<vector<bool> > dp(m+1, vector<bool>(n+1, false));
for (int i = 0; i <=m ;++i) {
for (int j = 0; j <=n; ++j) {
if (i==0 && j ==0) dp[i][j] = true;
else if (i == 0 && s2[j-1] == s3[j-1]) dp[i][j] = dp[i][j-1];
else if (j == 0 && s1[i-1] == s3[i-1]) dp[i][j] = dp[i-1][j];
else if (s1[i-1] == s3[i+j-1] && s2[j-1] != s3[i+j-1]) {
dp[i][j] = dp[i-1][j];
}
else if (s2[j-1] == s3[i+j-1] && s1[i-1] != s3[i+j-1]){
dp[i][j] = dp[i][j-1];
}else if (s1[i-1] == s3[i+j-1] && s2[j-1] == s3[i+j-1]){
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
}
return dp[m][n];
}
};