leetcode：97. 交错字符串（java 回溯）

r囧r小猫 2021-09-28 09:56 337阅读 0赞

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
    示例 1:
    输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
    输出: true
    示例 2:
    输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
    输出: false

第1种方法回溯法时间复杂度肯定是很不理想的

public boolean isInterleave(String s1, String s2, String s3) {
            if(s3.length()!=s1.length()+s2.length())return false;
            return dfs(0, 0, 0, s1, s2, s3);
        }
    
        public boolean dfs(int index, int s1i, int s2i, String s1, String s2, String s3) {
            if (index == s3.length() && s1i == s1.length() && s2i == s2.length()) {
                return true;
            }
            if (s1i > s1.length() || s2i > s2.length() || index > s3.length()) {
                return false;
            }
            char s1c = '!';
            char s2c = '!';
            char s3c = '!';
            if (s1i < s1.length()) {
                s1c = s1.charAt(s1i);
            }
            if (s2i < s2.length()) {
                s2c = s2.charAt(s2i);
            }
            if (index < s3.length()) {
                s3c = s3.charAt(index);
            }
            //两个字符都相等 分两种情况进行回溯
            if (s1c == s3c && s2c == s3c) {
                if (dfs(index + 1, s1i + 1, s2i, s1, s2, s3)) {
                    return true;
                } else {
                    return dfs(index + 1, s1i, s2i + 1, s1, s2, s3);
                }
            } else if (s1c == s3c) {
                return dfs(index + 1, s1i + 1, s2i, s1, s2, s3);
            } else if (s2c == s3c) {
                return dfs(index + 1, s1i, s2i + 1, s1, s2, s3);
            } else {
                return false;
            }
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，337人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 97. 交错字符串

设dp\[i\]\[j\]表示s1的前i个与s2的前j个，能否组成s3的前i+j个即可。 s1\[i\]与s2\[j\]必有一个在末尾。所以判断他们与s3\[i+j\]的关

- 日理万妓/ 2023年07月03日 04:40/ 0 赞/ 16 阅读

相关 leetcode 97交错的字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1: 输入: s1 = “aabcc”, s2 = “dbbca”, s3

墨蓝/ 2023年06月20日 06:14/ 0 赞/ 83 阅读

相关 leetcode97 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1: 输入: s1 = "aabcc", s2 = "dbbca", s3

忘是亡心i/ 2023年06月16日 12:00/ 0 赞/ 80 阅读

相关 LeetCode_97.交错字符串_没懂

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

港控/mmm°/ 2023年02月27日 13:48/ 0 赞/ 90 阅读

相关 Leetcode 97. 交错字符串

Leetcode 97. 交错字符串 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.c

梦里梦外;/ 2023年02月11日 10:20/ 0 赞/ 118 阅读

相关 LeetCode 97交错字符串(动态规划)

> 微信搜一搜：`bigsai` > [大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1] > 关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：

比眉伴天荒/ 2023年01月01日 14:48/ 0 赞/ 254 阅读

相关 97. 交错字符串

> 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。 > > 两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会

清疚/ 2022年10月10日 01:56/ 0 赞/ 266 阅读

相关 Leetcode 97. 交错字符串(DP)

题目重述给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串

喜欢ヅ旅行/ 2022年09月08日 03:44/ 0 赞/ 245 阅读

相关 LeetCode 97 交错字符串

题目：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。输入输出：输入: s1 = "aabcc", s2 = "d

ゞ浴缸里的玫瑰/ 2022年03月06日 15:12/ 0 赞/ 299 阅读

相关 leetcode：97. 交错字符串（java 回溯）

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1: 输入: s1 = "aabcc", s2 = "

r囧r小猫/ 2021年09月28日 09:56/ 0 赞/ 338 阅读