日韩不卡抠逼,国产骚逼草草,操喷久久久久久91

1.最長公共子序列
2.最長公共子串
3.最長回文串
4.最長回文序列
5.最長遞增序列
6.最長先增后減序列
7.(最短)編輯距離
8.子串匹配問題
9.通配符問題

1.最長公共子序列（longest common subsequence， LCS）

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

dp[i][j]表示字符串a(chǎn)的前i長度的子串a'，和b的前j個長度子串的b'的最長公共序列的長度

狀態(tài)轉(zhuǎn)移方程
$dp[i][j]= \begin{cases} dp[i-1][j-1]+1\space\space 當a[i-1] == b[i-1]時\\ max(dp[i-1][j],dp[i][j-1])\space\space 當a[i-1] != b[i-1]時 \end{cases}$

func LCS(a string, b string) int {
    dp := make([][]int, len(a)+1)
    for i, _ := range dp {
        dp[i] = make([]int, len(b)+1)
        if i == 0 {
            continue
        }
        for j, _ := range dp[i] {
            if j == 0 {
                continue
            }
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = dp[i-1][j]
                if dp[i][j-1] > dp[i][j] {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }

    return dp[len(a)][len(b)]
}

復雜度：
T = O(mn)
S = O(mn)

2.最長公共子串（longest common substring）

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

記a[0:i]為a前i個長度的子串，b[0:j]為b前j個長度的子串
dp[i][j]表示a[0:i]和b[0:j]的以二者最后一個字符結(jié)尾的最長公共子串的長度
比如a是god，b是goods，dp[3][4]就是2（od的長度），dp[3][5]就是0

轉(zhuǎn)移方程
$dp[i][j]= \begin{cases} dp[i-1][j-1]+1 \space\space 當a[i-1] == b[i-1]時\\ 0 \space\space 當a[i-1] != b[i-1]時 \end{cases}$

func LCSubstring(a string, b string) int {
    dp := make([][]int, len(a)+1)
    max := 0
    for i, _ := range dp {
        dp[i] = make([]int, len(b)+1)
        if i == 0 {
            continue
        }
        for j, _ := range dp[i] {
            if j == 0 {
                continue
            }
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = 0
            }
            if dp[i][j] > max {
                max = dp[i][j]
            }
        }
    }

    return max
}

暴力解

遍歷a，依次與b的所有字符比較，如果a[i]==b[j]，再比較a中a[i]開頭和b中b[j]開頭的子串。

func LCSubstring(a string, b string) int {
    max := 0
    for i, _ := range a {
        for j, _ := range b {
            if a[i] != b[j] {
                continue
            }
            for k := i + 1; k < len(a); k++ {
                for l := j + 1; l < len(b); l++ {
                    if a[i:k+1] == b[j:l+1] && k+1-i > max {
                        max = k + 1 - i
                    }
                }
            }
        }
    }
    
    return max
}

最壞復雜度 $O(m^2*n^2)$

廣義后綴數(shù)解

// 留坑

3.最長回文串

暴力解

遍歷每個字符串
以當前字符a[i]為中心，向兩邊探測是否兩側(cè)字符是否相同
以當前字符a[i]、a[i+1]為中心，向兩邊探測是否兩側(cè)字符是否相同

func LPSubstring(a string) int {
    max := 0
    for i := 0; i < len(a); i++ {
        j := 1
        for ; i+j < len(a) && i-j >= 0 && a[i+j] == a[i-j]; j++ {
        }
        if 2*j-1 > max {
            max = 2*j - 1
        }

        if i < len(a)-1 && a[i] == a[i+1] {
            k := 1
            for ; i+1+k < len(a) && i-k >= 0 && a[i+1+k] == a[i-k]; k++ {
            }
            if 2*k > max {
                max = 2 * k
            }
        }
    }

    return max
}

時空復雜度
時間復雜度，最壞情況是整個字符串都由一個字符組成，每個字符都要向兩側(cè)探測到底。
T_worse = O(n^2)
S = O(1)

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

長度為1的子串，肯定是回文串
長度為2的子串，如果兩字符相同，則是回文串
長度超過2的子串，如果首位字符相同，且首位之間也是回文串，則是回文串

設(shè)dp[i][j]表示起點為a[i]，終點為a[j]的子串是否為回文串
轉(zhuǎn)移方程
$dp[i][j]= \begin{cases} 當j==i\space時，true \space\space \\ 當j==i+1時，\space\space 若a[i]==a[j], true。否則false \\ 當j>=i+2時，\space\space 若a[i]==a[j] 且 dp[i+1][j-1],true。否則false \\ \end{cases}$

當子串長度大于2時要依賴前面求解過的結(jié)果

試著推一下。假設(shè)有字符串abcdcf：
i=0,j=0，長度為1，true
i=0,j=1，長度為2，false
i=0,j=2，長度為3，需要判斷a和c是否相同，如果相同，要依賴a[1][1]，但是a[1][1]不知道
所以i 遞增，j 遞增這個順序推不行

換個方向：i 遞增，j 遞減
i=0,j=5，依賴a[1][4]，a[1][4]結(jié)果還沒有出來，所以也不行

再換個方向：i 遞減，j 遞增
i=5,j=5，長度為1，無依賴
i=4,j=4，長度為1，無依賴
i=4,j=5，長度為2，無依賴
i=3,j=3，長度為1，無依賴
i=3,j=4，長度為2，無依賴
i=3,j=5，長度為3，依賴a[4][4]，a[4][4]已經(jīng)出來了，a[3][5]可以推出

所以i 遞減，j 遞增這個方向推是可行的

微信圖片_20220929134821.jpg

func LPSubstring(a string) int {
    dp := make([][]bool, len(a))
    max := 0
    for i := len(dp) - 1; i >= 0; i-- {
        dp[i] = make([]bool, len(a))
        for j := i; j < len(dp[i]); j++ {
            // 長度為1的子串肯定是回文串
            if j == i {
                dp[i][j] = true
                continue
            }
            // 長度為2的子串，倆字符相同即為回文串
            if j == i+1 {
                dp[i][j] = a[i] == a[j]
                continue
            }
            // 長度超過2的子串，倆字符相同且二者之間滿足回文，則為回文串
            dp[i][j] = a[i] == a[j] && dp[i+1][j-1]
            if dp[i][j] && j-i+1 > max {
                max = j - i + 1
            }
        }
    }

    return max
}

復雜度
T(n) = O(n^2)
S(n) = O(n^2)

原串倒序+求解最長公共子串

將原來的字符串倒序，再求倒序串和原串的最長公共子串。如原串a(chǎn)badcf，倒序成fcdaba，求二者的最長公共子串。

馬拉車算法(Manacher Algorithm)

該算法也是動態(tài)規(guī)劃。
先假設(shè)存在的所有回文子串的長度都是奇數(shù)，所以對稱中心是一個元素。
dp[i]表示以a[i]為對稱中心的最長回文串的長度
用c、r分別表示目前發(fā)現(xiàn)的右邊界最靠右的回文串的對稱中心的位置，右邊界的位置
初始c=0, r = 0
遍歷原串，當前位置i一定滿足i>=c，如果i<r，說明i處在一個對稱的子串中

19f420a79ca4d4a9aaaac0516341cee.jpg

i關(guān)于c的對稱點為i'，以i'為中心的最長回文串的左邊界 Li'
如果Li' > r'，dp[i] = dp[i']
如果Li' <= r'，則說明dp[i]至少 >=r，然后以i為中心，r-i+1為起點距離向兩邊探測，如果發(fā)現(xiàn)在i串的右邊界r之外，則更新c和r。
這樣利用對稱性就避免了從距離1開始向兩側(cè)探測。

如果i=r，沒有捷徑可走了，只能以i為中心點向外探測，探測完成后更新c和r
如果i>r，只能以i為中心點向外探測，探測完成后更新c和r

預處理原串，插入n+1個分割字符，將abadcf處理成_a_b_a_d_c_f_
現(xiàn)在所有的回文串長度都是奇數(shù)了，如a，_a_

func Manacher(a string) int {
    b := "_"
    for _, n := range a {
        b += string(n) + "_"
    }

    c := 0
    r := 0
    max := 0

    dp := make([]int, len(b))
    for i, _ := range dp {
        if i < r {
            i2 := 2*c - i // i的對稱點
            if i+(dp[i2]-1)/2 < r {
                dp[i] = dp[i2]
            } else {
                j := r - i + 1
                for ; i+j < len(b) && i-j >= 0 && b[i+j] == b[i-j]; j++ {
                }

                if i+j-1 > r {
                    r = i + j - 1
                    c = i
                }

                dp[i] = 2*j - 1
                if dp[i] > max {
                    max = dp[i]
                }
            }
            continue
        }
        j := 1
        for ; i+j < len(b) && i-j >= 0 && b[i+j] == b[i-j]; j++ {
        }
        if i+j-1 > r {
            r = i + j - 1
            c = i
        }

        dp[i] = 2*j - 1
        if dp[i] > max {
            max = dp[i]
        }
    }

    return (max - 1) / 2
}

復雜度
T(n) = O(2n) = O(n) // 確定每個dp[i]需要O(n)，r從0增長到n-1也需要O(n)
S(n) = O(n)

4.最長回文序列

暴力解

有 $2^n$ 個子序列，檢測其是否回文為序列，然后記錄下最長的，所以暴力解基本不行。

原串倒序+求解原串和倒序串的最長公共子序列

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

設(shè)dp[i][j]表示子串以i為起點，j為終點的子串的最長回文序列。
轉(zhuǎn)移方程：
$dp[i][j]= \begin{cases} dp[i+1][j-1]+2 \space\space 當a[i]==a[j]\space時\\ max(dp[i][j-1], dp[i+1][j])，\space\space 當a[i]!=a[j]\space時 \\ \end{cases}$
dp[i+1][j-1]表示的是i~j之間的子串的最優(yōu)值，也就是去掉頭尾i、j。應(yīng)該注意判斷子串的有效性，如i==j時，[i+1][j-1]這樣的子串是不存在的。所以細化一下狀態(tài)方程可以寫成這樣：
$dp[i][j]= \begin{cases} j=i時，1\\ j=i+1時， \begin{cases} 若a[i]=a[j]，則為2\\ 0 \end{cases} \\ j>= i+2時， \begin{cases} 若a[i]=a[j]，則為dp[i+1][j-1]+2\\ max(dp[i][j-1], dp[i+1][j]) \end{cases} \end{cases}$

同樣需要i逆推，j正推

func LPS(a string) int {
    dp := make([][]int, len(a))
    for i := len(dp) - 1; i >= 0; i-- {
        dp[i] = make([]int, len(a))
        for j := i; j < len(a); j++ {
            if j == i {
                dp[i][j] = 1
                continue
            }
            if j == i+1 {
                if a[i] == a[j] {
                    dp[i][j] = 2
                } else {
                    dp[i][j] = 0
                }
                continue
            }
            if a[i] == a[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                max := dp[i][j-1]
                if dp[i+1][j] > max {
                    max = dp[i+1][j]
                }
                dp[i][j] = max
            }
        }
    }

    return dp[0][len(a)-1]
}

復雜度
T(n) = O(n^2)
S(n) = O(n^2)

5.最長遞增序列

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

設(shè)dp[i]表示以i結(jié)尾的遞增子序列的長度。
求取dp[i]:

首先dp[i]肯定至少為1
遍歷0~i-1的元素，如果其中一個元素a[j]的取值小于a[i]，那a[j]+1就是a[j]的一個可能的取值，求出這些可能中的最大值即可

轉(zhuǎn)移方程：
$dp[i] = max(dp[j]+1)，0 <= j < i，并且a[j] < a[i]$

func LongestIncreaseSequence(arr []int) int {
    dp := make([]int, len(arr))
    dp[0] = 1
    for i := 1; i < len(arr); i++ {
        dp[i] = dp[i-1]
        for j := 0; j < i; j++ {
            if arr[j] < arr[i] && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
    }

    return dp[len(arr)-1]
}

復雜度
T(n) = O(n^2)
S(n) = O(n)

二分查找

比如輸入序列為arr := []int{1,5,2,3,9}
弄一個輔助數(shù)組a，初始值是輸入序列的第一項
然后從index=1開始遍歷arr，當前值為v， a的最后一項記作a.tail

如果v>a.tail，則將v添加到a后面，成為a的最后一項
如果v<=a.tail，則利用二分查找定位到a中第一個大于v的元素k，用v替換k

最終a的長度就是最長序列的長度。這很好理解，a就是被最長序列拓寬的。

func LongestIncreaseSequence(arr []int) int {
    b := []int{arr[0]}

    for i := 1; i < len(arr); i++ {
        if arr[i] > b[len(b)-1] {
            b = append(b, arr[i])
        } else if arr[i] < b[len(b)-1] {
            k := binarySearch(b, arr[i])
            b[k] = arr[i]
        }
    }
    return len(b)
}

func binarySearch(b []int, v int) int {
    // 找出切片b中，第一個大于v的元素的位置
    left := 0
    right := len(b) - 1

    for right > left {
        mid := (left + right) / 2
        if b[mid] < v {
            left = mid + 1
        } else {
            right = mid
        }
    }

    if b[left] < v {
        return -1 // 沒有找到
    }

    return left
}

復雜度
T(n) = O(nlogn)
S(n) = O(n)

6.最長先增后減序列

只要這個序列滿足先遞增，后遞減就行，不要求中心點兩邊的數(shù)量一樣多

先求遞增+再求遞減

先求出以i結(jié)尾的遞增序列長度，在求出以i為起點的遞減序列長度，兩個長度之和-1，就是以i為最高點的序列的先增后減序列的長度。

?？途W(wǎng)-合唱隊問題

7.(最短)編輯距離

Levenshtein 距離，又稱編輯距離，指的是兩個字符串之間，由一個轉(zhuǎn)換成另一個所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。編輯距離的算法是首先由俄國科學家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如：
字符串A: abcdefg
字符串B: abcdef
通過增加或是刪掉字符 ”g” 的方式達到目的。這兩種方案都需要一次操作。把這個操作所需要的次數(shù)定義為兩個字符串的距離。
要求：
給定任意兩個字符串，寫出一個算法計算它們的編輯距離

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

設(shè)有字符串A、B
A[0:i]表示A的 [0,i) 這個區(qū)間組成的字符串
設(shè)dp[i][j]表示A[0:i]和字符串B[0:j](最短)編輯距離，如dp[1][1]表示a的首字符編輯成b的首字符

當兩個子串的末字符相同時，dp[i][j] = dp[i-1][j-1]

可以用反正法證明一下：
假設(shè)dp[i][j]不等于dp[i-1][j-1]
也就是A[0:i]和B[0:j]存在比dp[i-1][j-1]更優(yōu)的解K，K<dp[i-1][j-1]
也就是經(jīng)過K次編輯A[0:i]和B[0:j]相同，此時A[0:i-1]和B[0:j-1]也相同
也就是A[0:i-1]和B[0:j-1]也存在更優(yōu)解K<dp[i-1][j-1]
與題設(shè)dp[i-1][j-1]為A[0:i-1]和B[0:j-1]的最優(yōu)解矛盾

當兩個子串的末字符不相同時

微信圖片_20220930174240.jpg

A→B有幾種可能：
A'→B'，然后a→b
A'+a → B'，然后后面補充一個b
A'→B'+b，然后刪除末尾的a
此時最優(yōu)值在三種情況中取最小

func MinEditDistance(a string, b string) int {
    dp := make([][]int, len(a)+1)
    for i, _ := range dp {
        dp[i] = make([]int, len(b)+1)
        for j, _ := range dp[i] {
            if i == 0 {
                dp[i][j] = j
                continue
            }
            if j == 0 {
                dp[i][j] = i
                continue
            }
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                min := dp[i-1][j-1] + 1
                if dp[i][j-1]+1 < min {
                    min = dp[i][j-1] + 1
                }
                if dp[i-1][j]+1 < min {
                    min = dp[i-1][j] + 1
                }
                dp[i][j] = min
            }
        }
    }
    return dp[len(a)][len(b)]

}

復雜度
T(n) = O(m*n)
S(n) = O(m*n)

牛客網(wǎng)-計算編輯距離

8.子串匹配問題

在主串中尋找子串，如在主串s = "abcde" 中尋找子串sub = "ab"，如果找到，返回首次出現(xiàn)位置，如果不存在，返回-1

暴力解：

指針i遍歷主串，j遍歷子串，當失配時，從i+1開始令j=0重新比較

func SearchSubstring(s string, sub string) int {
    i := 0
    j := 0
    for i < len(s) && j < len(sub) {
        if s[i] == sub[j] {
            i++
            j++
        } else {
            i = i + 1
            j = 0
        }
    }

    if j == len(sub) {
        return i - len(sub)
    }

    return -1
}

最壞復雜度，每次都要比較到子串的最后一個字符才發(fā)現(xiàn)不匹配，如aaaaaaaaab，aaab。
T_worse = O((n-m+1)*m) = O((n-m)*m)

KMP算法（Knuth-Morris-Pratt Algorithm)

再看一下暴力破解過程，假如主串指針走到i、子串指針走到j時，發(fā)生了失配，然后就從i的下一個位置（即i+1）開始，把子串從頭到尾重新比較。

主串： | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? |...
子串： | a | b | c | a | b | ?|...
假設(shè)當 j = 5 時出現(xiàn)失配，說明j前面的部分是和主串吻合的
主串： | a | b | c | a | b | ? | ? | ? | ? | ? | ? |...
子串： | a | b | c | a | b | ? |...
按照暴力算法是從主串當前起始點的下一位開始從頭比較
主串： | a | b | c | a | b | ? | ? | ? | ? | ? | ? |...
子串： ----| a | b | c | a | b | ? |...

上帝視角可以發(fā)現(xiàn)，i+1這個位置根本不用比較，因為此時的第一位b和a就對不上，同樣i+2這個位置也不用，因為c和a也是第一位就對不上。只有走到i+3，才有可能匹配。
主串： | a | b | c | a | b | ? | ? | ? | ? | ? | ? |...
子串： ------------| a | b | c | a | b | ? |...

這就是kmp的特點，主串指針i不用回頭，將子串指針j回頭到某個位置即可。（此時前兩位a=a，b=b是確定的，所以j也不用直接回到0。）

當j在某個位置發(fā)生失配，需要知道j的下一跳應(yīng)該跳到哪個位置繼續(xù)，假設(shè)這個信息存在一個叫next的表中，并且我們已經(jīng)得到了next表。此時程序應(yīng)該這么寫：

func KMP(a string, b string) (allMatches []int) {
    i := 0
    j := 0

    next := buildNext(b)
    for i < len(a) {
        if j == len(b) {
            allMatches = append(allMatches, i-len(b))
            j = 0
        }
        if a[i] == b[j] {
            i++
            j++
        } else {
            if j == 0 { // 如果在子串首字符就失配，應(yīng)將主串指針右移，子串指針不變
                i++
            } else {
                j = next[j]
            }
        }

    }

    return
}

重點是如何構(gòu)造next表

主串： | a | b | - | a | b | ? |...
子串： | a | b | - | a | b | ? |...

主串： | a | b | c | - | - | - |a |b| c| ? |...
子串： | a|b| c| - | - | - | a | b | c | ? |...

主串： | a | b | c | - | - | - | - | - |a |b| c| ? |...
子串： | a|b| c| - | - | - | - | - | a | b | c | ? |...

只要把前面標紅的一截和后面標紅的一截對齊，這段標紅的區(qū)域叫做最長公共前后綴，j從紅色區(qū)域的下一個字符開始比較。

字符串s的前綴的定義是：起點為0，終點在最后一個字符前的子串。比如abc的前綴有兩個a、ab，類似地，后綴有c、bc。一個前綴和一個后綴相同，這就是一個公共前后綴。比如abcab的最長公共前后綴是ab。

next[j]是在j失配時的下一跳位置，也是sub[0:j]的最長公共前后綴長度。比如由sub="abcde"構(gòu)建的next表，next[2]表示在c發(fā)生失配時的下一跳，也表示ab的最長公共前后綴長度。所以有些編碼中也把next table叫prefix table。

假如sub="aaacd"，要求解的內(nèi)容是：
next[1] 表j=1失配時的下一跳，也是a的最長公共前后綴，0
next[2] 表j=2失配時的下一跳，也是aa的最長公共前后綴，1
next[3] 表j=3失配時的下一跳，也是aaa的最長公共前后綴，2
next[4] 表j=4失配時的下一跳，也是aaac的最長公共前后綴，0

構(gòu)造next表不需要暴力解，可以遞推出來。
首先next[1]肯定是0，當next[k]已經(jīng)求解出來后，直接比較最長公共前后綴的下一字符是否相同，如果相同，那就可以構(gòu)成一個更長的公共前后綴。所以next[k+1] = next[k]+1。就像下面的兩個問號代表的內(nèi)容如果相同，就可以形成長度為3公共前后綴。
| a | b | ? | ... | a | b | ? |...

如果不同的話，說明無法構(gòu)成一個更長的公共前后綴，就要嘗試是否能構(gòu)成更短的。

如下，因為e和b不同，所以無法形成長度為5的公共前后綴

| a | b | c | a | e | ... | a | b | c | a | b |
|-----(1)-----|-------|-----(2)-----|

于是可以在(2)尋找一個后綴，使得它等于(1)一個前綴，然后驗證此時是否能為末尾的b找到相同的元素。因為(1)和(2)是相同的，所以相當于在(1)中找最大公共前后綴，直接讀取next[4]就知道了，此時next[4]值為1，所以問題又回到了上面的比較公共前后綴的下一字符是否相同。

如果相同，最長公共前后綴+1
如果不同，繼續(xù)在后綴中找更小的后綴，比較下一字符是否相同...
直到末字符匹配上了或者找到的next[x]是0

func buildNext(sub string) []int {
    next := make([]int, len(sub))
    for i := 2; i < len(sub); i++ {
        l := next[i-1]
        for l != 0 && sub[l] != sub[i-1] {
            l = next[l]
        }

        if sub[l] == sub[i-1] {
            next[i] = l + 1
        } else {
            next[i] = 0
        }
    }

    return next
}

構(gòu)造next表可以看成在sub中，從i=1開始從搜索自己的前綴

func buildNext2(sub string) []int {
    next := make([]int, len(sub))
    i := 1
    j := 0

    for i < len(sub)-1 {
        if sub[i] == sub[j] {
            next[i+1] = j + 1
            i++
            j++
            continue
        }
        if j == 0 {
            next[i+1] = 0
            i++
        } else {
            j = next[j]
        }
    }

    fmt.Println(next)
    return next
}

9.字符串通配符

定義：
?匹配一個字符
*匹配任意多個字符，可以為0個，同樣
能被*和?匹配的字符僅由英文字母和數(shù)字0到9組成
給出一個字符串s，一個通配符表達式p，請判斷這個字符串是否完全匹配這個通配符。
比如abb匹配a*b，abc不匹配a*b。

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

dp[i][j]表示s[0:i]是否匹配p[0:j]，0<= i <= len(s)，0<= j <= len(p)

遞推關(guān)系：
如果p[j-1]是個普通字符：

s[i-1]和p[j-1]相同，并且dp[i-1][j-1]為true，則dp[i][j]為true
否則false

如果p[j-1]是"?"

s[i-1]為字母或數(shù)字，并且dp[i-1][j-1]為true，則dp[i][j]為true
否則false

如果p[j-1]是"*"，有兩種情況可以判定dp[i][j]為true，其余則為false

當dp[i-1][j]為true時，并且最后這個字符是數(shù)字或字母。
(也就是因為ab*可以匹配abc，所以它也能匹配abcd，abcde...)
如果dp[i][j-1]為true，此時"*"可以解讀為空字符，所以為true，如ab和ab*

func IsMatch(p string, s string) bool {
    dp := make([][]bool, len(s)+1)
    // dp[i][j]表示s的前i個字符和模式p的前j個字符是否匹配
    for i, _ := range dp {
        dp[i] = make([]bool, len(p)+1)
        for j, _ := range dp[i] {
            if i == 0 {
                if j == 0 {
                    dp[i][j] = true
                } else {
                    if p[j-1] == '*' {
                        dp[i][j] = dp[i][j-1]
                    } else {
                        dp[i][j] = false
                    }
                }
                continue
            }

            if j == 0 {
                dp[i][j] = false
                continue
            }

            pj := p[j-1]
            si := s[i-1]

            if pj == '?' {
                dp[i][j] = dp[i-1][j-1] && (isLetter(si) || isNumber(si))
                continue
            }

            if pj == '*' {
                dp[i][j] = (dp[i-1][j] && (isLetter(si) || isNumber(si))) || dp[i][j-1]
                continue
            }

            dp[i][j] = dp[i-1][j-1] && lower(pj) == lower(si)
        }
    }

    return dp[len(s)][len(p)]
}

func isLetter(n byte) bool {
    return (n >= 'a' && n <= 'z') || (n >= 'A' && n <= 'Z')
}

func isNumber(n byte) bool {
    return n >= '0' && n <= '9'
}

func lower(n byte) string {
    return strings.ToLower(string(n))
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

字符串的幾個問題

字符串的幾個問題

1.最長公共子序列（longest common subsequence， LCS）

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

2.最長公共子串（longest common substring）

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

暴力解

廣義后綴數(shù)解

3.最長回文串

暴力解

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

原串倒序+求解最長公共子串

馬拉車算法(Manacher Algorithm)

4.最長回文序列

暴力解

原串倒序+求解原串和倒序串的最長公共子序列

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

5.最長遞增序列

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

二分查找

6.最長先增后減序列

先求遞增+再求遞減

7.(最短)編輯距離

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

8.子串匹配問題

暴力解：

KMP算法（Knuth-Morris-Pratt Algorithm)

9.字符串通配符

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

字符串的幾個問題

1.最長公共子序列（longest common subsequence， LCS）

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

2.最長公共子串（longest common substring）

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

暴力解

廣義后綴數(shù)解

3.最長回文串

暴力解

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

原串倒序+求解最長公共子串

馬拉車算法(Manacher Algorithm)

4.最長回文序列

暴力解

原串倒序+求解原串和倒序串的最長公共子序列

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

5.最長遞增序列

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

二分查找

6.最長先增后減序列

先求遞增+再求遞減

7.(最短)編輯距離

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

8.子串匹配問題

暴力解：

KMP算法（Knuth-Morris-Pratt Algorithm)

9.字符串通配符

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

1.最長公共子序列（longest common subsequence， LCS）