首页 > 代码库 > 交叉字符串
交叉字符串
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
样例
比如 s1 = "aabcc" s2 = "dbbca"
- 当 s3 = "aadbbcbcac"，返回 true.
- 当 s3 = "aadbbbaccc"， 返回 false.
dp[i][j][k] 代表 当到了s3的第i位时，s1的到了第j位 s2到了第k位。 因为i是一直向前循环的 且 只用到i-1 所以可以省去第一维数组 又因为 i == k+j 所以可以省第三层循环 最终时间复杂度 空间复杂度都为 O(N^2)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 class Solution { 6 public: 7 /* 8 * @param : A string 9 * @param : A string10 * @param : A string11 * @return: Determine whether s3 is formed by interleaving of s1 and s212 */13 int dp[210][210];14 bool isInterleave(string s1, string s2, string s3) {15 // write your code here16 if(s3.length() != s1.length() + s2.length()) return 0;17 18 dp[0][0] = 1; 19 for(int i = 1; i <= s3.length(); ++i){20 for(int j = 0; j <= min(i, (int)s1.length()); ++j){21 int k = i - j;22 23 if(j > 0 && s3[i-1] == s1[j-1]){24 dp[j][k] = dp[j][k] | dp[j-1][k];25 }26 27 if(k > 0 && s3[i-1] == s2[k-1]){28 dp[j][k] = dp[j][k] | dp[j][k-1];29 }30 31 }32 }33 return dp[s1.length()][s2.length()] == 1;34 }35 };36 37 int main(){38 string a , b ,c;39 cin >> a >> b >> c;40 Solution sol = Solution();41 bool ans = sol.isInterleave(a, b, c);42 cout << ans << endl;43 }
交叉字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。