给定串s1,s2,计算s3是否为s1和s2顺序叠加的串。
这个题开始模拟,但是有一个问题,如果s1[p1]和s2[p2]同时都等于s3[p3]怎么办,这个时候如果选择的话就需要预存状态然后开始搜索。
果然超时。
网上有人说用DP
f[i][j] = f[i-1][j] + s1[i] && s1[i] == s3[k]
f[i][j] = f[i][j-1](i+j = k) && s2[j] == s3[j]
s3串中的第k个字符完全匹配是需要s1串中的第i个字符或者s2串中的第j个字符相等才行。
枚举所有情况,最多n^2
输出f[i][j] i = s1.length() j = s2.length() i+j = s3.length()即可。
class Solution { public: bool ***f; bool isInterleave(string s1, string s2, string s3) { if(s1.length() + s2.length() != s3.length())return false;<br /> bool f[500][500]; for(int i = 0;i < 500;i++) { for(int j = 0;j < 500;j++) { f[i][j] = false; } } f[0][0] = true; for(int i = 1;i <= s3.length();i++) { for(int j = 0;j < i;j++) { if(f[j][i-1-j] && i-1-j<=s2.length() && j+1 <= s1.length() && s1[j] == s3[i-1]) { f[j+1][i-1-j] = true; } if(f[j][i-1-j] && j <= s1.length() && i-1-j+1 <= s2.length() && s2[i-1-j] == s3[i-1]) { f[j][i-1-j+1] = true; } } } return f[s1.length()][s2.length()]; } };