97 Interleaving String

renweihub 發布于2019-08-14 17:59 / 1115人閱讀

摘要：和一樣給出和兩種方法。使用可以避免初始化的和結果的混淆。

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;
    }
}

云服務器 GPU云服務器 Interleaving memory interleaving 97rb my97 datepicker

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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