赞
踩
如果你从本文中学习到丝毫知识,那么请您点点关注、点赞、评论和收藏
大家好,我是爱做梦的鱼,我是东北大学大数据实验班大三的小菜鸡,非常渴望优秀,羡慕优秀的人,个人博客为:爱做梦的鱼https://zihao.blog.csdn.net/,微信公众号、微信视频号为【程序猿干货铺】,qq交流群为:1107710098,
如果你同样热爱算法,那么请关注我,我将每日更新力扣的每日一题的题解+代码,每周更新力扣周赛题解+代码
《本题Python代码版》
专栏《力扣每日一题》
专栏《力扣周赛》
专栏《力扣大厂模拟面试算法题》
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
有能力的同学先去看看官方题解吧,没有能力的话你会发现看了个寂寞
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/interleaving-string/solution/jiao-cuo-zi-fu-chuan-by-leetcode-solution/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
这道题可以转化成路径问题,类似于62.不同路径这道题
题目中给出的示例 1为:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例一可以转化为如下图,每次只能往右走或往下走,请问是否存在从start到end的路径,路径不唯一
target的每个字符都是从s1(向下)或者s2(向右)拿到的,所以只要判断是否存在这条target路径即可;
于是可定义boolean[][] dp ,dp[i][j]代表s1前i个字符与s2前j个字符拼接成s3的i+j字符,也就是存在目标路径能够到达i,j;
状态方程:
边界1:dp[0][0] = true
;
边界2:if i=0 : dp[0]dp[j] = s2[0-j) equals s3[0,j)
遇到false后面可以直接省略
边界3:if j=0 : dp[i]dp[0] = s1[0-i) equals s3[0,i)
遇到false后面可以直接省略
其他情况,到达(i,j)可能由(i-1,j)点向下一步,选择s1[i-1]到达;也可能由(i,j-1)点向右一步,选择s2[j-1]到达;
dp[i,j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])
代码一:未优化空间
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int s1Len = s1.length();
int s2Len = s2.length();
int s3Len = s3.length();
if (s1Len+s2Len!=s3Len){
return false;
}
// 初始化数组默认全为false
boolean[][] dp = new boolean[s1Len+1][s2Len+1];
dp[0][0] = true;
for (int i = 0; i <= s1Len; ++i) {
for (int j = 0; j <= s2Len; ++j) {
int p = i+j-1;
// 可看作整个dp数组从左上移动到右下,右下就是答案,代表了遍历完整个s3数组
if (i>0){
// 右移了
// 向右探索一步,添加一个s1的字符看看是否符合s3在该位置的值
// 前提得是探索之前是true说明前面的组成的临时s3字串与s3中对应的字符相同
dp[i][j] = dp[i][j] || (dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(p));
}
if (j>0){
// 向下移动
// 向下探索一步,添加一个s2的字符看看是否符合s3在该位置的值
// 前提得是探索之前是true说明前面的组成的临时s3字串与s3中对应的字符相同
dp[i][j] = dp[i][j] || (dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(p));
}
}
}
return dp[s1Len][s2Len];
}
public static void main(String[] args) {
// String s1 = "aabcc";
// String s2 = "dbbca";
// String s3 = "aadbbcbcac";
// System.out.println(new Solution1().isInterleave(s1,s2,s3));
boolean [] s1 = new boolean[6];
for (int i = 0; i < s1.length; i++) {
System.out.println(s1[i]);
}
}
}
复杂度分析
时间复杂度:O(nm),两重循环的时间代价为 O(nm)。n为s1长度,m为s2长度
空间复杂度:O(nm),存放状态的db矩阵
代码二:使用滚动数组优化空间复杂度(还没写)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。