[LeetCode] Interleaving

interleaving常用於error code correction

wireless communication、memory access 等可能會用到ECC的地方都可以看到他的蹤跡

其實麻將拿牌、撲克牌發牌照順序輪流發的概念就是interleaving

把可能連續的好牌(error)打散、洗的比較乾淨狀況下

大家的好牌(error)就不會過度集中、對於ECC來說比較容易校正

只能說古人真的很厲害

就來看看這題吧

這題應該是個DP的題目，所以先建個table

先把邊邊填好

從左上方[1][1]出發～～就看看上面看看左邊～

看看先前的s1 or s2 字是不是已經用過了～然後比對目前對應的自是不是相同

一路看看能不能最後走到右下方（用掉兩個string最後一個字母）

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        
        
        if(s3.length() != s1.length() + s2.length())
            return false;
        
        int len1 = s1.size(), len2 = s2.size();
        
        bool DPmap[s1.size()+1][s2.size()+1];
        
        DPmap[0][0] = true;
        
        for(int i = 1 ; i < len1+1; i++)
             DPmap[i][0] = (DPmap[i-1][0] && s1[i-1] == s3[i-1]);
        for(int j = 1 ; j < len2+1; j++)
             DPmap[0][j] = (DPmap[0][j-1] && s2[j-1] == s3[j-1]);
       
        for(int i = 1; i < len1+1; i++)
            for(int j = 1; j < len2+1; j++) 
                DPmap[i][j] = (DPmap[i][j-1] && s2[j-1] == s3[i+j-1]) || (DPmap[i-1][j] && s1[i-1] == s3[i+j-1]);
        
        return DPmap[len1][len2];
    }
};

class Solution {

public:

bool isInterleave(string s1, string s2, string s3) {

if(s3.length() != s1.length() + s2.length())

return false;

int len1 = s1.size(), len2 = s2.size();

bool DPmap[s1.size()+1][s2.size()+1];

DPmap[0][0] = true;

for(int i = 1 ; i < len1+1; i++)

DPmap[i][0] = (DPmap[i-1][0] && s1[i-1] == s3[i-1]);

for(int j = 1 ; j < len2+1; j++)

DPmap[0][j] = (DPmap[0][j-1] && s2[j-1] == s3[j-1]);

for(int i = 1; i < len1+1; i++)

for(int j = 1; j < len2+1; j++)

DPmap[i][j] = (DPmap[i][j-1] && s2[j-1] == s3[i+j-1]) || (DPmap[i-1][j] && s1[i-1] == s3[i+j-1]);

return DPmap[len1][len2];

}

};

下週預計發個提拉米蘇DIY ＆北區第一次指考模擬考的數甲分析

如果工作順利的話….

[LeetCode] Interleaving

請按讚：

相關

發表者：user

分享此文：

請按讚：

相關

發表者：user