锐客网

  1. 首页 > it技术 > >

LeetCode|【LeetCode】Interleaving String && CSDN 交替字符串

算法dpleetcode字符串leetcode解题报告

1、Interleaving String
Total Accepted: 6431 Total Submissions: 34519 My Submissions
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.
2、交替字符串
题目详情
如果字符串str3能够由str1和str2中的字符按顺序交替形成，那么称str3为str1和str2的交替字符串。例如str1="abc"，str2="def"，那么"adbecf", "abcdef", "abdecf", "abcdef", "adefbc"等等都为str1和str2的交替字符串。更形式化的，str3的生成算法如下：
str3=""
while str1不为空 or str2不为空:
把str1或str2的首字符加入到str3,并从str1或str2中删除相应的字符
end
给定str1, str2,和str3，判断str3是否为str1和str2的交替字符串。
输入格式：
多组数据，每组数据三行，分别是str1,str2,str3。str1,str2的长度在[1..100]范围内，str3的范围在[1..200]范围内。字符串只包含小写英文字母。
输出格式：
每组数据输出一行YES或者NO。
答题说明
输入样例
a
b
ab
a
b
ca
输出样例：
YES
NO
解题思路：
这俩道题一样的。str1和str2可以组成的情况非常多，如果一一列举判断是否在范围内，肯定超时。
还是dp吧，因为是有序的，所以递推公式
dp[i][j] = (dp[i-1][j] && (s1.charAt(i-1) == s3.charAt(i+j-1))) || (dp[i][j-1] && (s2.charAt(j-1) == s3.charAt(i+j-1)));
1、Java AC

public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int len1 = s1.length(); int len2 = s2.length(); int len = s3.length(); if(len1 + len2 != len){ return false; } int size = 1000; boolean dp[][] = new boolean[size][size]; dp[0][0] = true; for(int i = 1; i <= len1; i++){ dp[i][0] = dp[i-1][0] && (s1.charAt(i-1) == s3.charAt(i-1)); } for(int j = 1; j <= len2; j++){ dp[0][j] = dp[0][j-1] && (s2.charAt(j-1) == s3.charAt(j-1)); } for(int i = 1; i <= len1; i++){ for(int j = 1; j <= len2; j++){ dp[i][j] = (dp[i-1][j] && (s1.charAt(i-1) == s3.charAt(i+j-1))) || (dp[i][j-1] && (s2.charAt(j-1) == s3.charAt(i+j-1))); } } return dp[len1][len2]; } }

2、C++ AC

#include #include #include using namespace std; const int maxn = 300; char s1[maxn]; char s2[maxn]; char s3[maxn]; bool dp[maxn][maxn]; int i, j; bool isInterleave() { int len1 = strlen(s1); int len2 = strlen(s2); int len = strlen(s3); if (len1 + len2 != len) { return false; } dp[0][0] = true; for (i = 1; i <= len1; i++) { dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]); } for (j = 1; j <= len2; j++) { dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]); } for (i = 1; i <= len1; i++) { for (j = 1; j <= len2; j++) { dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) || (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1])); } } return dp[len1][len2]; }int main(){while(scanf("%s",s1) != EOF){ scanf("%s",s2); scanf("%s",s3); bool flag = isInterleave(); printf("%s\n",flag == true ? "YES" : "NO"); } return 0; }

【LeetCode|【LeetCode】Interleaving String && CSDN 交替字符串】

    推荐阅读


    上一篇：Spyder debug调试文件，如何传入参数

    下一篇：其他|机器人工具箱-6自由度机器人建模