LCS问题Leetcode583,712

港控/mmm° 2022-01-05 06:21 158阅读 0赞

LCS问题，关于字符串下的，最长公共子序列。

最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

原先的思路是用动态规划去做。

状态： dp(m,n）为s1中0-m，s2 0-n子串中最长的公共子序列的长度值。

转移方程 dp\[m,n\] = dp\[m-1,n-1\] +1 ; s1\[m\]==s2\[n\]

dp\[m,n\] = max(dp\[m,n-1\],dp\[m-1,n). s1\[m\]!=s2\[n\];

边界： dp\[m,n\] =0; 当x=0或y = 0时。

712

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

示例 1:

输入: s1 = "sea", s2 = "eat"  
输出: 231  
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。  
在 "eat" 中删除 "t" 并将 116 加入总和。  
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。  
示例 2:

输入: s1 = "delete", s2 = "leet"  
输出: 403  
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，  
将 100\[d\]+101\[e\]+101\[e\] 加入总和。在 "leet" 中删除 "e" 将 101\[e\] 加入总和。  
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。  
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

1.第一种思路：

状态： s\[i,j\]为s1 0..i s2 0..j 为止的需要删除的ascii码最小和的值。

转移方程：这里刚开始我的思维有问题，写成了s\[i\]\[j\] = min(s\[i-1\]\[j\],s\[i\]\[j-1\]+s1\[i\]+s2\[j\]). 错误的，这样写不就是不管左右，都删除当前的s1\[i\],s2\[j\].为什么会犯错？第一动态规划写的不太多，第二，思维思考的不全面，自以为想出来的就是对的，其实应该反复揣摩。

正确的写法： s\[i\]\[j\] = min(s\[i-1,j\]+s1\[i\],s\[i\]\[j-1\]+s2\[j\])，这个当s\[i-1\]\[j\]时，代表s1缩小，即删除s1的字符所以要加上s1\[i\].所以加上s2\[j\]理所当然。

class Solution {
    public:
        int minimumDeleteSum(string s1, string s2) {
            
            if(s1.size()==0)
            {
                int res = 0;
                for(int i = 0;i<s2.size();i++)
                    res += s2[i];
                return res;
            }
            if(s2.size()==0){
                int res = 0;
                for(int i = 0;i<s1.size();i++)
                    res += s1[i];
                    return res;
            }
            
            vector<vector<int>> s(s1.size()+1,vector<int>(s2.size()+1,0));
           
            for(int i = 0;i<s1.size();i++){
                
                s[i+1][0] = s[i][0]+s1[i];
            }
            for(int j = 0;j<s2.size();j++){
                s[0][j+1] = s[0][j]+s2[j];
            }
           
            
            for(int i = 0;i<s1.size();i++){
                for(int j =0;j<s2.size();j++){
                    
                    if(s1[i]==s2[j]){
                        //0  s[1][1]
                        s[i+1][j+1] = s[i][j];
                    }else
                        s[i+1][j+1] = min(s[i][j+1]+s1[i],s[i+1][j]+s2[j]);
                    
                }
                
            }
            int m = s1.size();
            int n = s2.size();
            return s[m][n];
            
        }
    };

2.可是有人去删除两个同时不成立的情况。

这种思路其实是删除同时不成立的情况，其实没必要，因为在解空间树中，第一种情况能包含第二种，所以第一种能通过。

相应的加了后，反而会增加程序的时间。

class Solution {
    public:
        int minimumDeleteSum(string s1, string s2) {
            
            if(s1.size()==0)
            {
                int res = 0;
                for(int i = 0;i<s2.size();i++)
                    res += s2[i];
                return res;
            }
            if(s2.size()==0){
                int res = 0;
                for(int i = 0;i<s1.size();i++)
                    res += s1[i];
                    return res;
            }
            
            vector<vector<int>> s(s1.size()+1,vector<int>(s2.size()+1,0));
           
             for(int i = 0;i<s1.size();i++){
                
                s[i+1][0] = s[i][0]+s1[i];
            }
            for(int j = 0;j<s2.size();j++){
                s[0][j+1] = s[0][j]+s2[j];
            }
            
            for(int i = 0;i<s1.size();i++){
                for(int j =0;j<s2.size();j++){
                    
                    if(s1[i]==s2[j]){
                        //0  s[1][1]
                        s[i+1][j+1] = s[i][j];
                    }else
                        s[i+1][j+1] = min(s[i][j+1]+s1[i],min(s[i+1][j]+s2[j],s[i][j]+s1[i]+s2[j]));
                    
                }
                
            }
            int m = s1.size();
            int n = s2.size();
            return s[m][n];
            
        }
    };

Leetcode 583.

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例 1:

输入: "sea", "eat"  
输出: 2  
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

思路：就是利用Lcs 得到相同的子串长度，再将两串s1 s2相加再减去 2\*得到的长度

class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m = word1.size(),n = word2.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(word1[i-1]==word2[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 n+m-2*dp[m][n];
            
        }
    };