動態(tài)規(guī)劃問題（2）——尋找最長公共子串

wushuiyong 發(fā)布于2019-08-21 11:27 / 3013人閱讀

摘要：題目給定兩個(gè)字符串求出它們的最長公共字串說明比如在單詞和它們的最長公共子序列是。最長公共子串和最長公共子序列的區(qū)別。

題目

給定兩個(gè)字符串,求出它們的最長公共字串

var str1="abcdefg";
var str2="xyzabcd";

說明：比如在單詞"abcdefg"和"abcdefg"它們的最長公共子序列是"abcd"。尋找最長子序列常用于遺傳學(xué)中，用于使用核苷酸堿基的首字母對DNA的描述（這段話從網(wǎng)上抄的）。

最長公共子串和最長公共子序列的區(qū)別。

最長公共子串和最長公共子序列的區(qū)別為：子串是串的一個(gè)連續(xù)的部分，子序列則是從不改變序列的順序，而從序列中去掉任意的元素而獲得新的序列；也就是說，子串中字符的位置必須是連續(xù)的，子序列則可以不必連續(xù)。

這道題，想了很長時(shí)間，終于慢慢的把題目做出來了，接下來的內(nèi)容可能會很難理解，也許我比較笨吧至少對我來說想了好久。我會盡量結(jié)合圖文去展示解題的思路，也可以自己想想，然后在看接下來的內(nèi)容。

暴力破解

其實(shí)看到這個(gè)問題我們直接可以用暴力的方式解決這個(gè)問題。給定兩個(gè)字符串A和B，我們可以通過從A的第一個(gè)字符開始與B對應(yīng)的每一個(gè)字符進(jìn)行對比的方式找到最長的公共字串。如果此時(shí)沒有找到匹的字母，則移動到A的第二個(gè)字符處，然后從B的第一個(gè)字符處進(jìn)行對比，以此類推。由于下面的內(nèi)容較多，爆力方法我這里就不寫了。

動態(tài)規(guī)劃

我們回顧一下動態(tài)規(guī)劃的解題思路：

從底部開始解決問題，將所有小問題解決掉，然后合并成一個(gè)整體的解決方案。

使用一個(gè)數(shù)組建立一張表，用于存放被分解成眾多子問題的解。

那基于這兩點(diǎn)我們首先要分解這個(gè)問題，怎么分解呢？

第一步： 最小的是每個(gè)字符，所以要把分解成單個(gè)的字符去匹配每個(gè)單個(gè)的字符。因此這里我們可以得到下面這一張表：

匹配為1，不匹配為0，這個(gè)時(shí)候我們就分解成為每個(gè)字符的匹配情況，由此得到。

第二步： 每個(gè)子問題有了，這個(gè)時(shí)候我們要建立一個(gè)數(shù)組去存放每個(gè)子問題的解。關(guān)鍵問題在于，我們怎么樣把每個(gè)子問題的解存起來，并且可以得到我們想要的結(jié)果。對表做一些處理，初始化一個(gè)二維數(shù)組：

var arr = new Array(str1.length + 1);
for (var i = 0; i <= str1.length + 1; i++) {
    arr[i] = new Array(str2.length + 1);
    for (var j = 0; j <= str2.length + 1; j++) {
        arr[i][j] = 0;
    }
}

得到如下的表：

圖中我們可以看到行和列都多加了一個(gè)并且都是0，這是為了判斷上一個(gè)是否相等的操作，后面你就會明白它的意思了。

對初始化的二維數(shù)組坐些處理，得到如下圖：

一開始看到這個(gè)圖的時(shí)候你可能會很懵逼，如果你已經(jīng)看明白了，那你就跳過我這段廢話吧。我們應(yīng)該一直的告訴自己，新建的這個(gè)數(shù)組是存放每個(gè)子問題的解，首先要明確的是找出最長字串，有哪些方式可以做到把字串從原來的字符串中截取，所以要知道起始位置和字串的長度。從圖中可以看到的紅字就是存放這個(gè)位置的最優(yōu)解字串的長度，所以應(yīng)該建立兩個(gè)變量去存儲其實(shí)位置的index 和最大長度 maxLen 。得到一下代碼：

var maxLen = 0;
var index = 0;
for(var i = 0; i <= str1.length; i++){
    for(var j = 0; j <= str2.length; j++){
        if(i == 0 || j == 0){
            arr[i][j] = 0
        }else{
            if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            }else{
                arr[i][j] = 0;
            }
        }
        if(arr[i][j] > maxLen){
            maxLen = arr[i][j];
            index = i;
        }
    }
}

簡單的解釋一下，這里要明確連續(xù)的字串的位置，是二維數(shù)組對角線上的值，這點(diǎn)明確了很多問題就好理解了。

上面的代碼把最主要的兩個(gè)參數(shù)找到了，那接下來就是選擇其中的一個(gè)字符串去截取字串：

var str = "";
if(maxLen == 0){
    return "";
}else{
    for(var k = index - maxLen; k < maxLen; k++){
        str += str1[k];
    }
    return str;
}

下面貼上完整的代碼，你也可以去我的github上查看源碼；

function LCS(str1, str2){
    var maxLen = 0;
    var index = 0;

    var arr = new Array();
    for (var i = 0; i <= str1.length + 1; i++) {
        arr[i] = new Array();
        for (var j = 0; j <= str2.length + 1; j++) {
            arr[i][j] = 0;
        }
    }

    for(var i = 0; i <= str1.length; i++){
        for(var j = 0; j <= str2.length; j++){
            if(i == 0 || j == 0){
                arr[i][j] = 0
            }else{
                if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                }else{
                    arr[i][j] = 0;
                }
            }
            if(arr[i][j] > maxLen){
                maxLen = arr[i][j];
                index = i;
            }
        }
    }

    var str = "";
    if(maxLen == 0){
        return "";
    }else{
        for(var k = index - maxLen; k < maxLen; k++){
            str += str1[k];
        }
        return str;
    }
}
var str1="abcdefg";
var str2="xyzabcd";
LCS(str1, str2)     // abcd

到此為止我們終于找到了最長公共字串。到這里我們需要想想能不能在優(yōu)化了，雖然這樣解決問題，但是引入了一個(gè)二維數(shù)組，在兩個(gè)字符串都較大的情況下不是很劃算，是否可以進(jìn)一步優(yōu)化？答案是可以的，需要改變一下策略，是否可以建立一個(gè)一維數(shù)組就可以解決問題了呢，這里晚了先寫這么多把，之后我會在公眾號中貼出暴力解法和動態(tài)規(guī)劃的優(yōu)化解法，歡迎持續(xù)關(guān)注我的公眾號獲得一手的信息。

歡迎關(guān)注微信公眾賬號查看最新文章