leetcode97. Interleaving String

dmlllll 发布于2019-08-15 10:58 / 557人阅读

摘要：题目要求输入数组和判断是不是由和中的元素交替组成的。思路一乍一看这题可以通过递归的方式来求解。而走到和对应的中的也是确定的。这里我们利用数组记录判断情况。所以我们可以将的二维数组简化为一维数组的数据结构。提高空间的利用率。

题目要求

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.

输入数组s1,s2和s3,判断s3是不是由s1和s2中的元素交替组成的。

思路一：backtracking

乍一看这题可以通过递归的方式来求解。我们可以同时判断当前下标s1和s2的元素是不是和s3当前下标的元素相同。如果相同，就进入下一轮递归。
代码如下：

    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length() + s2.length() != s3.length()) return false;
        return isInterleave(s1, s2, s3, 0,0,0);
    }
    
    public boolean isInterleave(String s1, String s2, String s3, int pointer1, int pointer2, int pointer3){
        if(pointer1==s1.length() && pointer2==s2.length())return pointer3 == s3.length();
        if(pointer1
这段代码 不出意外的 超时了
因为这里有太多的重复调用了。很多的判断在第一次递归的过程中就可以知道，数组在走到s1和s2中的某个位置pointer1，pointer2时会进入死胡同。而走到pointer1和pointer2对应的s3中的pointer3也是确定的。所以如果我们可以利用这部分信息，就可以省略掉很多重复的判断。这里我们利用boolean[][]数组记录判断情况。
    public boolean isInterleave2(String s1, String s2, String s3) {
        if(s1.length() + s2.length() != s3.length()) return false;
        return isInterleave(s1, s2, s3, 0,0,0, new boolean[s1.length()+1][s2.length()+1]);
        
    }
    
    public boolean isInterleave(String s1, String s2, String s3, int pointer1, int pointer2, int pointer3, boolean[][] isInvalid){
        if(isInvalid[pointer1][pointer2]) return false;
        if(pointer3 == s3.length())return true;
        boolean isValid = pointer1
dynamic programming
同样适用boolean[][]作为存储临时值的数据结构，这里我们将其代表的含义改变为至下标(i,j)时是否可以和前(i-1,j)或是(i,j-1)上的值连接满足s3。
解释如下：在这里(i,j)位置值的含义代表如果采用s2的前i个值和s1的前j个值，是否可以组成s3前i+j个值。所以判断(i,j)需要参考(i-1,j)和(i,j-1)位置上的值。如果(i-1,j)成立，也就是说s2的前i-1个值和s1的前j个值可以组成s3前i+j-1个值，那么如果s2的第i个值等于s3的第i+j个值，那么该式子成立。（i,j-1）也是同理的。
    public boolean isInterleave3(String s1, String s2, String s3){
        if ((s1.length()+s2.length())!=s3.length()) return false;
        boolean[][] matrix = new boolean[s2.length()+1][s1.length()+1];
        matrix[0][0] = true;
        for(int i = 1 ; i
最后的简化
在上一种思路中，我们可以看到，其实在每一层的遍历中只有上一层数据和前一个数据对当前数据有参考价值。所以我们可以将boolean[][]的二维数组简化为boolean[]一维数组的数据结构。提高空间的利用率。
    public boolean isInterleave4(String s1, String s2, String s3){
        if ((s1.length()+s2.length())!=s3.length()) return false;
        boolean[] matrix = new boolean[s2.length()+1];
        for(int i = 0 ; i<=s1.length() ; i++){
            for(int j = 0 ; j<=s2.length() ; j++){
                if(i==0&&j==0){
                    matrix[j] = true;
                }else if(i==0){
                    matrix[j] = matrix[j-1] && s2.charAt(j-1)==s3.charAt(j-1);
                }else if(j==0){
                    matrix[j] = matrix[j] && s1.charAt(i-1) == s3.charAt(i-1);
                }else{
                    matrix[j] = (matrix[j-1] && s2.charAt(j-1)==s3.charAt(i+j-1))
                            || (matrix[j] && s1.charAt(i-1)==s3.charAt(i+j-1));
                }
            }
        }
        return matrix[s2.length()];
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 LeetCode_String Interleaving memory interleaving Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67461.html

leetcode-98- Interleaving String

97. Interleaving StringDescriptionHintsSubmissionsDiscussSolutionGiven s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example,Given:s1 = aabcc,s2 = dbbca, When s3 = aadbbc...

jackwang 2019-07-31 11:03 评论0 收藏0
97 Interleaving String

摘要：和一样给出和两种方法。使用可以避免初始化的和结果的混淆。 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 s...

renweihub 2019-08-14 17:59 评论0 收藏0
[LintCode] Interleaving Positive and Negative Numb

摘要：注意，若正数多于负数，则序列以正数开始，正数结束。所以先统计正数个数，若超过序列长度的一半，则正指针从开始，反之则负指针从开始。注意交换函数的形式，必须是交换指针所指数字的值，而非坐标。 Problem Given an array with positive and negative integers. Re-range it to interleaving with positiv...

calx 2019-08-14 15:22 评论0 收藏0
LeetCode - 009 - 回文数（palindrome-number）

摘要：最后，我们判断一开始的两种情况，并返回或者即可。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-05-22 19:30:42 Recently revised in 2019-05-23 11:42:52 一目录不折腾的前端，和咸鱼有什么区别目录一目录二前言三解题 3.1 解题 - 数组操作 ...

hikui 2019-05-23 16:23 评论0 收藏0
LeetCode - 007 - 整数反转（reverse-integer）

摘要：详细介绍将其他值转成数字值。此方法更改数组的长度。详细介绍解题思路首先，将传入的数字转换成字符串，并分割成数组。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-05-19 09:42:39 Recently revised in 2019-05-19 16:08:24 Hello 小伙伴们，如果觉得本文还不错，记得给个 star ，小伙伴们...

venmos 2019-05-22 18:23 评论0 收藏0