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]; } };
下週預計發個提拉米蘇DIY & 北區第一次指考模擬考的數甲分析
如果工作順利的話….