leetcode97. Interleaving String

dmlllll 發布于2019-08-15 10:58 / 558人閱讀

摘要：題目要求輸入數組和判斷是不是由和中的元素交替組成的。思路一乍一看這題可以通過遞歸的方式來求解。而走到和對應的中的也是確定的。這里我們利用數組記錄判斷情況。所以我們可以將的二維數組簡化為一維數組的數據結構。提高空間的利用率。

題目要求

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()];
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

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

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