97 Interleaving String

renweihub 发布于2019-08-14 17:59 / 984人阅读

摘要：和一样给出和两种方法。使用可以避免初始化的和结果的混淆。

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.

和edit distance一样给出dp和memorized search两种方法。memorized search速度更快。

public boolean isInterleave(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 < matrix[0].length; i++){
        matrix[0][i] = matrix[0][i-1]&&(s1.charAt(i-1)==s3.charAt(i-1));
    }

    for (int i = 1; i < matrix.length; i++){
        matrix[i][0] = matrix[i-1][0]&&(s2.charAt(i-1)==s3.charAt(i-1));
    }

    for (int i = 1; i < matrix.length; i++){
        for (int j = 1; j < matrix[0].length; j++){
            matrix[i][j] = (matrix[i-1][j]&&(s2.charAt(i-1)==s3.charAt(i+j-1)))
                    || (matrix[i][j-1]&&(s1.charAt(j-1)==s3.charAt(i+j-1)));
        }
    }

    return matrix[s2.length()][s1.length()];
}

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        char[] c1 = s1.toCharArray(), c2 = s2.toCharArray(), c3 = s3.toCharArray();
        int m = s1.length(), n = s2.length();
        if(m+n != c3.length) return false;
        return dfs(c1,c2,c3,0,0,0, new boolean[m+1][n+1]);
        
    }
    // 使用invalid可以避免boolean初始化的false和结果false的混淆。
    public boolean dfs(char[] c1, char[] c2, char[] c3, int i, int j, int k, boolean[][] invalid){
        if(invalid[i][j]) return false;
        if(k == c3.length) return true;
        boolean valid = 
            i < c1.length && c1[i] == c3[k] && dfs(c1,c2,c3,i+1,j,k+1, invalid) ||
            j < c2.length && c2[j] == c3[k] && dfs(c1,c2,c3,i,j+1,k+1, invalid);
        if(!valid) invalid[i][j] = true;
        return valid;
    }
}

服务器托管私有云 Interleaving memory interleaving 97rb my97 datepicker

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

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

leetcode97. Interleaving String

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

dmlllll 2019-08-15 10:58 评论0 收藏0
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
[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
protocol buff

摘要：协议使用简述是的一种数据交换的格式，它独立于语言，独立于平台。可以用于对象序列话，序列化协议也是一种协议。 protocol buff 协议使用 github:https://github.com/chengbingh...(https://github.com/chengbingh... 1 简述 protocol buff 是google 的一种数据交换的格式，它独立于语言，独立...

iflove 2019-08-15 15:26 评论0 收藏0
最简单的kubernetes HA安装方式-sealos详解

摘要：集群三步安装概述本文教你如何用一条命令构建高可用集群且不依赖和，也无需。通过内核对进行负载均衡，并且带健康检测。当然你也可以把用于一些其它场景，比如代理自己的服务等 kubernetes集群三步安装概述本文教你如何用一条命令构建k8s高可用集群且不依赖haproxy和keepalived，也无需ansible。通过内核ipvs对apiserver进行负载均衡，并且带apiserve...

spacewander 2019-06-28 17:11 评论0 收藏0