Problem
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 =
s2 =
Given:
s1 =
"aabcc"
,s2 =
"dbbca"
,
When s3 =
When s3 =
"aadbbcbcac"
, return true.When s3 =
"aadbbbaccc"
, return false.Code
bool isInterleave(string s1, string s2, string s3) { // Start typing your C/C++ solution below // DO NOT write int main() function int m = s1.size(); int n = s2.size(); if(s3.size() != m + n) return false; if(m == 0 && n == 0) return true; vector<vector<bool> > p(m + 1,vector<bool>(n + 1,false)); for(int i =1; i <= m; ++i) p[i][0] = (s3[i - 1] == s1[i - 1]); for(int j =1; j <= n; ++j) p[0][j] = (s3[j - 1] == s2[j - 1]); for(int i =1; i <= m; ++i){ for(int j =1; j <= n; ++j){ if(s1[i - 1] == s2[j - 1]){ if(s3[i + j - 1] == s1[i - 1]) p[i][j] = p[i - 1][j] || p[i][j - 1]; else p[i][j] = false; } else{ if(s3[i + j - 1] == s1[i - 1]) p[i][j] = p[i - 1][j]; else if(s3[i + j - 1] == s2[j - 1]) p[i][j] = p[i][j - 1]; else p[i][j] = false; } } } return p[m][n]; }
No comments:
Post a Comment