"求是否存在",毫无疑问,又是一道动态规划题。设当前子序列为S1[0..i]
,S2[0..j]
,S3[0..i+j+1]
,dp[i+1][j+1]==true
表示S3[0..i+j]
可以由S1[0..i]
和S2[0..j]
交叉组成,得到如下状态推导公式:
- 如果
S1[i]==S3[i+j+1]&&S2[j]!=S3[i+j+1]
,那么dp[i+1][j+1] = dp[i][j+1]
- 如果
S1[i]!=S3[i+j+1]&&S2[j]==S3[i+j+1]
,那么dp[i+1][j+1] = dp[i+1][j][k+1]
- 如果
S1[i]==S3[i+j+1]&&S2[j]==S3[i+j+1]
,那么dp[i+1][j+1] = dp[i][j+1]||dp[i+1][j]
- 如果
S1[i]!=S3[i+j+1]&&S2[j]!=S3[i+j+1]
,那么dp[i+1][j+1] = false
- 基准1:
dp[0][0]=true
- 基准2:
dp[0][1..len2]
和dp[1..len1][0]
注意:如果S1的最大下标为i,S2最大下标为j,那么合并S1和S2之后的最大下标为i+j+1
代码如下:
class Solution { public: /** * * @param s1 string字符串 * @param s2 string字符串 * @param s3 string字符串 * @return bool布尔型 */ bool isInterleave(string s1, string s2, string s3) { // write code here int a = s1.size(), b = s2.size(), c = s3.size(); if (a + b != c) return false; vector<vector<bool> > dp(a+1, vector<bool>(b+1, false)); dp[0][0] = true; for (int i = 0; i < a && s1[i] == s3[i]; ++i) dp[i+1][0] = true; for (int i = 0; i < b && s2[i] == s3[i]; ++i) dp[0][i+1] = true; for (int i = 0; i < a; ++i) { for (int j = 0; j < b; ++j) { int m = s1[i], n = s2[j], o = s3[i+j+1]; if (m == o && n != o) dp[i+1][j+1] = dp[i][j+1]; if (m != o && n == o) dp[i+1][j+1] = dp[i+1][j]; if (m == o && n == o) dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j]; if (m != o && n != o) dp[i+1][j+1] = false; } } return dp[a][b]; } };