Description
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
The simplest way to solve this problem is DFS, whis has exponential time complexity.
Actually this is a problem that can be solved by a typical 2D DP solution.
Supposed that represent if can be interleaved by and , then
- ,
- if and
- or if and
- , otherwise
Then it is kind of obvious that 1-d array is enough. To make things clear, these two solutions are both shown below. The space complexity of the first one is , while that of the second one is (you can make with simple modifications).
Solution
1 class Solution {
2 public:
3 bool isInterleave(string s1, string s2, string s3) {
4 if (s1.size() + s2.size() != s3.size())
5 return false;
6
7 bool yes[s1.size()+1][s2.size()+1];
8 yes[0][0] = true;
9 for (int i = 1; i <= s1.size(); ++ i)
10 yes[i][0] = (s1[i-1] == s3[i-1]);
11
12 for (int i = 1; i <= s2.size(); ++ i)
13 yes[0][i] = (s2[i-1] == s3[i-1]);
14
15 for (int i = 1; i <= s1.size(); ++ i)
16 for (int j = 1; j <= s2.size(); ++ j)
17 yes[i][j] = (yes[i][j-1] && s2[j-1] == s3[i+j-1]) || \
18 (yes[i-1][j] && s1[i-1] == s3[i+j-1]);
19 return yes[s1.size()][s2.size()];
20 }
21
22 };It is not hard to find out that a 1-d array is enough.
1 // space complexity: O(n)
2 class Solution {
3 public:
4 bool isInterleave(string s1, string s2, string s3) {
5 if (s1.size() + s2.size() != s3.size())
6 return false;
7
8 bool yes[s2.size()+1];
9 yes[0] = true;
10
11 for (int i = 1; i <= s2.size(); ++ i)
12 yes[i] = (s2[i-1] == s3[i-1]);
13
14 for (int i = 1; i <= s1.size(); ++ i){
15 yes[0] = (s1[i-1] == s3[i-1]);
16 for (int j = 1; j <= s2.size(); ++ j)
17 yes[j] = (yes[j-1] && s2[j-1] == s3[i+j-1]) || \
18 (yes[j] && s1[i-1] == s3[i+j-1]);
19 }
20 return yes[s2.size()];
21 }
22
23 };