关于java:LeetCode097交错字符串

46次阅读

共计 1444 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交织组成的。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归

如果字符串长度都为 0 时，间接返回 true；

当 s1 的长度和 s2 的长度之和不等于 s3 的长度时，间接返回 false；

当 s1 的长度为 0 即 s1 曾经遍历完了，直接判断 s2 和 s3 是否相等；

当 s2 的长度为 0 即 s2 曾经遍历完了，直接判断 s1 和 s3 是否相等；

前面依据 s1 和 s2 的第一个字符是否和 s3 的第一个字符是否相等，递归调用该办法进行判断。

package com.kaesar.leetcode.LeetCode_051_100;

public class LeetCode_097 {
    /**
     * 递归
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public static boolean isInterleave(String s1, String s2, String s3) {
        // 当字符串长度都为 0 时，间接返回 true
        if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) {return true;}
        // 当 s1 的长度和 s2 的长度之和不等于 s3 的长度时，间接返回 false
        if (s1.length() + s2.length() != s3.length()) {return false;}
        // 当 s1 的长度为 0 即 s1 曾经遍历完了，直接判断 s2 和 s3 是否相等
        if (s1.length() == 0) {return s2.equals(s3);
        }
        // 当 s2 的长度为 0 即 s2 曾经遍历完了，直接判断 s1 和 s3 是否相等
        if (s2.length() == 0) {return s1.equals(s3);
        }
        if (s1.charAt(0) == s3.charAt(0) && s2.charAt(0) == s3.charAt(0)) {
            // 递归解决 s1 的下一个字符和 s2 和 s3 的下一个字符 && 递归解决 s1 和 s2 的下一个字符和 s3 的下一个字符
            return isInterleave(s1.substring(1), s2, s3.substring(1)) || isInterleave(s1, s2.substring(1), s3.substring(1));
        } else if (s1.charAt(0) == s3.charAt(0)) {
            //  递归解决 s1 的下一个字符和 s2 和 s3 的下一个字符
            return isInterleave(s1.substring(1), s2, s3.substring(1));
        } else if (s2.charAt(0) == s3.charAt(0)) {
            // 递归解决 s1 和 s2 的下一个字符和 s3 的下一个字符
            return isInterleave(s1, s2.substring(1), s3.substring(1));
        } else {
            // 当 s1 和 s2 的下一个字符和 s3 的下一个字符都不相等时，间接返回 false
            return false;
        }
    }

    public static void main(String[] args) {System.out.println(isInterleave("aabcc", "dbbca", "aadbbcbcac"));
    }
}