Interleaving String
Desicription
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.
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: bool isInterleave(string s1, string s2, string s3) { if(s1.size() + s2.size() != s3.size()) return 0; vector<vector<bool>> table(s1.size()+1, vector<bool>(s2.size()+1, 0)); for(int i = 0; i <= s1.size(); i++) { for(int j = 0; j <= s2.size(); j++){ if(!i && !j) table[i][j] = 1; else if(!i) table[i][j] = (table[i][j-1] && s2[j-1] == s3[i+j-1]); else if(!j) table[i][j] = (table[i-1][j] && s1[i-1] == s3[i+j-1]); else table[i][j] = ((table[i-1][j] && s1[i-1] == s3[i+j-1]) || (table[i][j-1] && s2[j-1] == s3[i+j-1])); } } return table[s1.size()][s2.size()]; } };
|