问题描述:
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc"
,
s2 = "dbbca"
,
When s3 = "aadbbcbcac"
, return true.
When s3 = "aadbbbaccc"
, return false.
原问题链接:https://leetcode.com/problems/interleaving-string/
问题分析
这个问题有一点复杂,主要在于要理清楚里面比较复杂的关系。在这里对于两个给定的字符串s1和s2来说,需要轮流从两个串里取一部分字符串作为合并后的串的一部分。因此,从通常的角度来看,必然是首先从一个串里取一截加入到合并的串里。那么具体该取哪个串呢?如果是从串的最开头,那么我们可以既取s1也取s2。而在中间的某个部分的时候,我们则需要交替的取了。
因此,为了解决这个问题,我们有两种思路来解决。
递归法
在开始的讨论里,我们已经看到,对于比较字段的匹配,我们可以是先取s1和目标串进行比较匹配,也可以开始是取s2来进行匹配。一旦某一个选定之后,我们就只能依次的选取后面的进行匹配了。所以假设在某个时候s1的当前位置是l1, s2的当前位置是l2, s3的当前位置是l3。那么我们就需要有一个元素来标识当前是已经匹配了哪个串的,到底是s1还是s2。这样就可以选择对应的串来和s3比较。
假定我们已经选定了某个串了,那么就要对它和s3进行比较。这个比较是满足什么样的关系呢?首先一个肯定是当前的字段要匹配。也就是说,假设当前s1位置是l1, s3的位置是l3,那么必然从l1到s1的末尾以及l3到s3的某位有一段是匹配的,可以匹配有1个或者多个元素。如果一个都不匹配,那么就应该返回false。
按照这个思路,我们得到如下的代码:
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if(s1.length() + s2.length() != s3.length()) return false; return isInterleave(s1, 0, s2, 0, s3, 0, true) || isInterleave(s1, 0, s2, 0, s3, 0, false); } public boolean isInterleave(String s1, int l1, String s2, int l2, String s3, int l3, boolean selected) { if(l1 == s1.length()) return s2.substring(l2).equals(s3.substring(l3)); if(l2 == s2.length()) return s1.substring(l1).equals(s3.substring(l3)); if(selected) { for(int i = 0; i < s1.length() - l1 && s1.charAt(l1 + i) == s3.charAt(l3 + i); i++) { if(isInterleave(s1, l1 + i + 1, s2, l2, s3, l3 + i + 1, false)) return true; } } else { for(int i = 0; i < s2.length() - l2 && s2.charAt(l2 + i) == s3.charAt(l3 + i); i++) { if(isInterleave(s1, l1, s2, l2 + i + 1, s3, l3 + i + 1, true)) return true; } } return false; } }
这种递归实现的方式效率并不高,因为它需要针对里面匹配的每个情况进行递归的看,其时间复杂度在极端情况下达到了O(2 ** n)。 所以在实际中运行的时候会导致超时的错误。
所以,这种办法虽然逻辑上正确,但是效率需要改进。
动态规划法
在前面递归方法的基础上,我们会很自然的想到要用动态规划这个办法来改进效率。在具体的实现里,我们定义一个boolean[m + 1][n + 1]的矩阵。其中m, n分别表示s1, s2的长度。这样矩阵里boolean[i][j]则分别表示当s1里i位置和s2里j位置时对应s3里i + j位置的匹配情况。
在i == 0或者j == 0的情况下,相当于单独的s1或者s2和s3进行比较匹配的情况。所以从递归的关系来说matrix[i][j] = matrix[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1) 或者
matrix[i][j] = matrix[i- 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)。
而对于其他的情况呢,则是这两种情况取或的关系。最终结果是返回matrix[m][n]。
根据上述讨论,详细的实现如下:
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if(s3.length() != s1.length() + s2.length()) return false; int m = s1.length(), n = s2.length(); boolean[][] matrix = new boolean[m + 1][n + 1]; for(int i = 0; i <= m; i++) for(int j = 0; j <= n; j++) { if(i == 0 && j == 0) matrix[i][j] = true; else if(i == 0) matrix[i][j] = matrix[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1); else if(j == 0) matrix[i][j] = matrix[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1); else matrix[i][j] = (matrix[i][j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) || (matrix[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)); } return matrix[m][n]; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum ...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
leetcode 1004 力码 去做 : array , dynamic-programming : link , math : string , sliding-window : array , median : string : string : number , reverse , bit : string : math , bit : string , ...
Leetcode:Leetcode提交
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
LeetCode 101:和你一起你轻松刷题(C++)
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
leetcode 持续刷leetcode中... 欢迎大家交流,也欢迎star. ...Leetcode 767: Reorganize String Leetcode 769: Max Chunks To Make Sorted Leetcode 792: Number of Matching Subsequences Leetcode 794: Valid
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...