字符串相关动态规划

algorithm

---

编辑距离

• 编辑距离
• 题目大意：两个字符串$s,t$，可以通过以下的三个操作，删除、替换、增加，使得两个字符串相等。假设每个操作的代价为1，那么通过上述三个操作，能够使得两个字符串相等的最小代价是多少？

思路1

$$dp[i][j] = \left\{\begin{matrix} dp[i-1][j-1] & s[i] == t[j] \\ min(dp[i-1][j],dp[i][j-1]) + 1 & s[i] \ne t[j] \\ \end{matrix}\right.$$

int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i = 0 ;i <= m ; i++) {
            dp[i][0] = i;
        }
        for(int j = 0; j<= n ;j++) {
            dp[0][j] = j;
        }
        for(int i = 1;i <= m; i++ ) {
            for(int j = 1; j <= n; j++) {
                int t = (word1[i-1] == word2[j-1]);
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1;
                dp[i][j] = min(dp[i][j] ,dp[i-1][j-1] + 1 - t );
            }
        }
        return dp[m][n];
}

• 时间复杂度:$O(m*n)$,空间复杂度：$O(m*n)$

两个字符串的删除ASCII最小值

• 两个字符串删除的ASCII最小值

思路1

$$dp[i][j] = \left\{\begin{matrix} dp[i-1][j-1] & s[i] == t[j] \\ min(dp[i-1][j]+s[i],dp[i][j-1] + t[j]) & s[i] \ne t[j] \\ \end{matrix}\right.$$

• 初始条件：$dp[i][0] = dp[i-1][0] + s[i],1\le i$

int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i = 1;i <= m ;i++) {
            dp[i][0] = dp[i-1][0] + s1[i-1];
        }
        for(int j = 1; j <= n ;j++) {
            dp[0][j]  = dp[0][j-1] + s2[j-1];
        }
        for(int i = 1; i <= m; i++) {
            for(int j =1 ;j <= n; j++) {
                if(s1[i-1] == s2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else 
                    dp[i][j] = min(dp[i-1][j] + s1[i-1] ,dp[i][j-1] + s2[j-1]);
            }
        }
        return dp[m][n];
}

• 时间复杂度:$O(m*n)$,空间复杂度：$O(m*n)$

两个字符串删除至相等的最小步数

• 删除的最小步数

思路1

$$dp[i][j] = \left\{\begin{matrix} dp[i-1][j-1] & s[i] == t[j] \\ min(dp[i-1][j],dp[i][j-1]) + 1 & s[i] \ne t[j] \\ \end{matrix}\right.$$

int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i = 1;i <= m; i++ ) {
            dp[i][0] = dp[i-1][0] +  1;
        }
        for(int j = 1; j <= n; j++ ) {
            dp[0][j] = dp[0][j-1] + 1;
        }
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n; j++) {
                if(word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = min(dp[i-1][j] ,dp[i][j-1]) + 1;
                }
            }
        }
        return dp[m][n];
    }

• 时间复杂度:$O(m*n)$,空间复杂度：$O(m*n)$

最长公共子序列

• 最长公共子序列

int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int m = A.size();
        int n = B.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(A[i-1] == B[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else 
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
}

• 时间复杂度:$O(m*n)$,空间复杂度：$O(m*n)$

子序列串

• 子序列串
• 题目大意：给定字符串s,t 并且$s.length < t.length$，问字符串s是否是t的一个子序列。

思路1

• 按照子序列的思想，决定s是否是t的子序列的基础条件是s[:i]是否是t[:j]的子序列，如果是，则继续扩展$s[:i+1]$或者$t[:j+1]$。
• 所以我们假设$dp[i][j]$表示$s[:i]$是否是$t[:j]$的子序列，那么对$dp[i+1][j+1]$，只有两种可能，一种是$s[i+1] == t[j+1]$，那么$dp[i+1][j+1]$取决于前面的子串$s[:i]$是否是$t[:j]$的子序列。第二种$s[i+1] != t[j+1]$ 那么$dp[i+1][j+1]$取决于$s[:i+1]$是否是$t[:j]$的子序列。
• 所以，综合两种情况：

$$dp[i][j] = \left\{\begin{matrix} dp[i-1][j-1] & s[i] = t[j] \\ dp[i][j-1] & s[i] \ne t[j] \\ \end{matrix}\right.\\ $$

• 初始情况：认为空串是任何串的子串，$dp[0][j] = 1;$

bool isSubsequence(string s, string t) {
        int m = s.size();
        int n = t.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int j = 0; j <= n; j++ ) { // 默认空串是任何字符串的子序列
            dp[0][j] = 1;
        }
        for(int i = 1; i<= m; i++ ) {
            for(int j = 1; j <= n; j++ ) {
                if(s[i-1] == t[j-1]) { // s[i]==t[j]
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[m][n];
}

• 时间复杂度：$O(m*n)$，空间复杂度：$O(m*n)$
  

最长字符串链

• 最长字符串链
• 题目大意：给定一个字符串数组，如果两个字符串$A,B$，如果$len(A) +1 == len(B)$，并且B可以通过A在任何位置插入一个字符构成B，那么认为A是B的前置字符串，如果有一系列的字符串满足这样的关系，那么认为这些字符串构成一条链，叫做字符串l链，现求最长的字符串链。

思路1

• 与最长递增子序列思路一致，这里是要满足最长的字符串链，可以认为最长递增子序列，限制条件是后面的数字大于前面的数，最长字符串链，限制的条件是两个字符串构成字符串链。
  $$dp[i] = \left\{\begin{matrix} \underset{0\le k \lt i}{max}\{dp[k] +1 \} & if \ w_k \ is \ pre_chain \ of \ w_i \\ 1 & else \end{matrix}\right.$$
• 初始条件：$dp[i] = 1;$

int longestStrChain(vector<string>& words) {
    sort(words.begin(),words.end(),[](string &s1,string &s2){return s1.length() < s2.length();});
    int n = words.size();
    vector<int> dp(n,1);
    int maxlen = 0;
    for(int i =1 ;i < n; i++ ) {
        for(int j = i-1; j >= 0; j-- ) {
            if( isprev(words[j] , words[i]) ) {
                dp[i] = max(dp[i] , dp[j] + 1);
            }
        }
        maxlen = max(maxlen,dp[i]);
    }
    return maxlen;
}
// 是否是构成链字符串的判断
int isprev(string& w1,string& w2) {
    if(w1.length() +1 != w2.length())
        return 0;
    unordered_map<string,int> umap;
    int n = w2.size();
    int m = w1.size();
    for(int i = 0 ;i < n ;i++ ) {
        string s2(w2.begin() + i + 1 ,w2.end());
        string s1(w2.begin(),w2.begin() + i);
        if(s1+s2 == w1)
            return 1;
    }
    return 0;
}

• 时间复杂度：$O(n^2)$，空间复杂度：$O(n)$，实际isprev函数占用空间和时间
• 可优化isprev函数