成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode97. Interleaving String

dmlllll / 565人閱讀

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

題目要求 
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.

輸入數(shù)組s1,s2和s3,判斷s3是不是由s1和s2中的元素交替組成的。

思路一：backtracking

乍一看這題可以通過遞歸的方式來求解。我們可以同時(shí)判斷當(dāng)前下標(biāo)s1和s2的元素是不是和s3當(dāng)前下標(biāo)的元素相同。如果相同，就進(jìn)入下一輪遞歸。
代碼如下：

    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

這段代碼 不出意外的 超時(shí)了


因?yàn)檫@里有太多的重復(fù)調(diào)用了。很多的判斷在第一次遞歸的過程中就可以知道，數(shù)組在走到s1和s2中的某個(gè)位置pointer1，pointer2時(shí)會(huì)進(jìn)入死胡同。而走到pointer1和pointer2對(duì)應(yīng)的s3中的pointer3也是確定的。所以如果我們可以利用這部分信息，就可以省略掉很多重復(fù)的判斷。這里我們利用boolean[][]數(shù)組記錄判斷情況。


    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[][]作為存儲(chǔ)臨時(shí)值的數(shù)據(jù)結(jié)構(gòu)，這里我們將其代表的含義改變?yōu)橹料聵?biāo)(i,j)時(shí)是否可以和前(i-1,j)或是(i,j-1)上的值連接滿足s3。
解釋如下：在這里(i,j)位置值的含義代表如果采用s2的前i個(gè)值和s1的前j個(gè)值，是否可以組成s3前i+j個(gè)值。所以判斷(i,j)需要參考(i-1,j)和(i,j-1)位置上的值。如果(i-1,j)成立，也就是說s2的前i-1個(gè)值和s1的前j個(gè)值可以組成s3前i+j-1個(gè)值，那么如果s2的第i個(gè)值等于s3的第i+j個(gè)值，那么該式子成立。（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
最后的簡化

在上一種思路中，我們可以看到，其實(shí)在每一層的遍歷中只有上一層數(shù)據(jù)和前一個(gè)數(shù)據(jù)對(duì)當(dāng)前數(shù)據(jù)有參考價(jià)值。所以我們可以將boolean[][]的二維數(shù)組簡化為boolean[]一維數(shù)組的數(shù)據(jù)結(jié)構(gòu)。提高空間的利用率。


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



想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67461.html

相關(guān)文章

  • 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 評(píng)論0 收藏0

  • 97 Interleaving String

    摘要：和一樣給出和兩種方法。使用可以避免初始化的和結(jié)果的混淆。 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 評(píng)論0 收藏0

  • [LintCode] Interleaving Positive and Negative Numb

    摘要：注意，若正數(shù)多于負(fù)數(shù)，則序列以正數(shù)開始，正數(shù)結(jié)束。所以先統(tǒng)計(jì)正數(shù)個(gè)數(shù)，若超過序列長度的一半，則正指針從開始，反之則負(fù)指針從開始。注意交換函數(shù)的形式，必須是交換指針?biāo)笖?shù)字的值，而非坐標(biāo)。 Problem Given an array with positive and negative integers. Re-range it to interleaving with positiv...

    calx 評(píng)論0 收藏0

  • LeetCode - 009 - 回文數(shù)（palindrome-number）

    摘要：最后，我們判斷一開始的兩種情況，并返回或者即可。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-05-22 19:30:42 Recently revised in 2019-05-23 11:42:52 一 目錄 不折騰的前端，和咸魚有什么區(qū)別 目錄 一 目錄 二 前言 三 解題 ?3.1 解題 - 數(shù)組操作 ...

    hikui 評(píng)論0 收藏0

  • LeetCode - 007 - 整數(shù)反轉(zhuǎn)（reverse-integer）

    摘要：詳細(xì)介紹將其他值轉(zhuǎn)成數(shù)字值。此方法更改數(shù)組的長度。詳細(xì)介紹解題思路首先，將傳入的數(shù)字轉(zhuǎn)換成字符串，并分割成數(shù)組。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-05-19 09:42:39 Recently revised in 2019-05-19 16:08:24 Hello 小伙伴們，如果覺得本文還不錯(cuò)，記得給個(gè) star ， 小伙伴們...

    venmos 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<