Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Have you met this question in a real interview? 

Yes

Example

For s1 = "aabcc", s2 = "dbbca"

• When s3 = "aadbbcbcac", return true.
• When s3 = "aadbbbaccc", return false.

Challenge

O(n2) time or better

class Solution { public: /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true of false. */ bool isInterleave(string s1, string s2, string s3) { // write your code here int m=s1.size(); int n=s2.size(); if (m+n!=s3.size()) return false; // i from s1 and j from s2 can form interleave s3 with i+j vector< vector > f(m+1, vector(n+1, false)); f[0][0]=true; for (int i=1; i<=m; i++){ f[i][0]= f[i-1][0] && s1[i-1]==s3[i-1]; } for (int i=1; i<=n; i++){ f[0][i]= f[0][i-1] && s2[i-1] == s3[i-1]; } for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ 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]); } } return f[m][n]; } };