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.
Subscribe to see which companies asked this question.
题解：
bool isInterleave(string s1, string s2, string s3) { int n1=s1.size(),n2=s2.size(),n3=s3.size(); if(n1+n2!=n3) return false; vector<int> mp(255,0); for(int i=0;i<n1;i++) mp[s1[i]]++; for(int i=0;i<n2;i++) mp[s2[i]]++; for(int i=0;i<n3;i++){ mp[s3[i]]--; if(mp[s3[i]]<0) return false; } vector<vector<int> >dp(n1+1,vector<int>(n2+1,0)); dp[0][0] = 1; for(int len = 1;len<=n3;len++){ for(int l=max(0,len-n2);l<=len&&l<=n1;l++){ if(l>0 && s1[l-1]==s3[len-1]) dp[l][len-l] |= dp[l-1][len-l]; if(len-l>0 && s2[len-l-1]==s3[len-1]) dp[l][len-l] |= dp[l][len-l-1]; } } return dp[n1][n2]==1; }