LeetCode-097-交错字符串

交错字符串

【LeetCode-097-交错字符串】题目描述:给定三个字符串 s1s2s3,请你帮忙验证 s3 是否是由 s1s2 交错 组成的。
示例说明请见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")); } }

【每日寄语】 碰到逆境时,应心生感激,这是可遇不可求啊!

    推荐阅读