“给定三个字符串s1、s2、s3,验证s3是否是s1和s2的交错组成的。”
题目链接:
来源:力扣(LeetCode)
链接:97. 交错字符串 - 力扣(LeetCode) (leetcode-cn.com)
给定三个字符串 s1、s2、s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:
提示:a + b 意味着字符串 a 和 b 连接。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
这道题比较容易想到的是用双指针来解题,指针p1指向字符串s1的头部,另一个指针p2指向字符串s2的头部,指针p3指向s3的头部,这样每次判断指针p1和p2指向的元素是否相同,相同则向后移动指针。
但是这种方法会出现错误,比如s1="aabcc",s2="dbbca",s3="aabbbcbcac"时,得到的结果是false,实际应该是true。
重新分析题意,如果s1+s2≠s3,那么s3必然不可能是s1和s2的交错,如果s1+s2=s3的时候就可以使用动态规划来求解:
代码参考:
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length(), m = s2.length(), t = s3.length();
if (n + m != t) {
return false;
}
boolean[] f = new boolean[m + 1];
f[0] = true;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
int p = i + j - 1;
if (i > 0) {
f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);
}
if (j > 0) {
f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
}
}
}
return f[m];
}
}
时间复杂度 : O(nm)
两重循环的时间代价为o(nm)。
空间复杂度: O(m)
空间复杂度为s2的长度。
这道题使用了动态规划解题,之后又用了滚动数组优化这个动态规划。
对于动态规划解题的相似题目还有: