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.
第一反应肯定要用DP的,用递归逻辑虽然简单,但肯定要超时的,但想着反正锻炼嘛,就先写了递归的。
吸取昨天微软面试的教训,发现纸上写代码还是不够简洁,尤其是不够细心,老是写到后边发现前边忘了什么东西,果不其然刚才纸上写递归的时候递归出口就忘写了,晕。
1.递归解法:
基本思路是用三个指针分别P1,P2,P3分别指向S1,S2,S3中的位置,P1往后P2往后是需要简直是否与P3往后匹配的,现在如果S3[P3]与S1,S2当前位置都不等,肯定是返回false,如果与s1当前位置匹配,那就尝试用p1+1往后递归匹配,如果与s2当前位置匹配,那就尝试用p2+1后的位置匹配,注意这两种情况成立一个就可以了;如果p1,p2其中一个先到底了,那就单独匹配另一个好了
代码如下:
bool isInterleave(string s1,string s2,string s3) { int n1=s1.length(),n2=s2.length(),n3=s3.length(); if ( n1+n2!=n3 ) return false; return _check(s1,0,s2,0,s3,0); } bool _check(const string& s1,int p1,const string& s2,int p2,const string& s3,int p3) { if ( p1==s1.size() ) return _compare(s2,p2,s3,p3); else if (p2==s2.size()) return _compare(S1,P1,S3,P3); bool ans=false; if (s3[p3]==s1[p1]) ans=_check(s1,p1+1,s2,p2,s3,p3+1); if (ans) return ans; if (s3[p3]==s2[p2]) ans=_check(s1,p1,s2,p2+1,s3,p3+1); } bool _compare(const string& s1,int p1,const string& s2,int p2) { while(p1!=s1.size()&&p2!=s2.size()) { if (s1[p1]!=s2[p2]) return false; p1++; p2++; } if ( p1!=s1.size()||p2!=s2.size()) return false; return true; }
2.DP版本解法
首先我们定义 f (i ,j )表示 s1的前i个字符和s2的前j个字符是否能组成s3的前(i+j)个字符,结果是1表示能组成,0表示不可以。
现在我们考虑把s1中第i+1个字符放进来,很明显 f (i+1,j) = 1的条件是 f(i,j) && s1[i+1] == s3[i+j+1],对吧~
所以我们可以得到状态转移方程是(这里i,j表示的是第i,j个字符,不是下标哈,所以换做下标的时候要-1):
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] ) ) ? 1 : 0;
注意为了防止越界的问题我们多加了外边一圈,用来表示某一个字符串是空的时候的情况:
代码如下:
bool isInterleave(string s1,string s2,string s3) { int n1=s1.length(),n2=s2.length(),n3=s3.length(); if ( n1+n2!=n3 ) return false; vector<vector<int> > dp(n1+1,vector<int>(n2+1,0) ); dp[0][0]=1; int i ,j; for(i=1;i<=n1;i++) dp[i][0]=dp[i-1][0]&&s1[i-1]==s3[i-1]?1:0; for(j=1;j<=n2;j++) dp[0][j]=dp[0][j-1]&&s2[j-1]==s3[j-1]?1:0; for(i=1;i<=n1;i++) for(j=1;j<=n2;j++) { if ((dp[i-1][j]&&s1[i-1]==s3[i+j-2]) || (dp[i][j-1]&&s2[j-1]==s3[i+j-2])) dp[i][j]=1; } return dp[n1][n2]; }