leetcode 712

野性酷女 2021-09-29 04:46 259阅读 0赞

这道题的思路：我是根据最长公共子序列的思路得来的。

**最长公共子序列**是： d\[i\]\[j\]表示字符串s1前i个（0～i-1）字符，和字符串s2前j个（0～j-1）字符的最长公共子序列。

分情况讨论：

当s1\[i-1\] == s2\[j-1\]的时候，d\[i\]\[j\] = d\[i-1\]\[j-1\]+1; 这个表示 ，当第i-1个字符相同时，就在之前d\[i-1\]\[j-1\]的长度上加一

当s1\[i-1\] != s2\[j-1\]的时候，d\[i\]\[j\] 的值就有可能有两种情况：

（1）d\[i\]\[j\] = d\[i-1\]\[j\]，表示d\[i\]\[j\]这个最长公共子序列，没有字符串s1\[i-1\]。那么就是相当于字符串s1（0～i-2）和字符串s2（0～j-1）的最长公共子序列

（2）d\[i\]\[j\] = d\[i\]\[j-1\],  表示d\[i\]\[j\]这个最长公共子序列，没有字符串s2\[i-1\]。那么就是相当于字符串s1（0～i-1）和字符串s2（0～j-2）的最长公共子序列

综上，d\[i\]\[j\] = max(d\[i-1\]\[j\],d\[i\]\[j-1\])

根据上面的这种思路，思考712这道题，这道题的意思是，删除字符，使得两个字符串相等，删除的字符相加起来，使得删除字符串的和最小。

可以设 d\[i\]\[i\] 表示字符串s1前i个（0～i-1）字符和字符串s2前j个（0～j-1）字符保持相等的**删除字符最小和**

那么对于d\[i\]\[j\] 也是分情况讨论：

当s1\[i-1\] ==s2\[j-1\] , 这就表示不需要删除s1\[i-1\]和s2\[j-1\]，则d\[i\]\[j\] = d\[i-1\]\[j-1\]

当s1\[i-1\]!=s2\[j-1\],  两个字符都不要 ，则d\[i\]\[j\] = d\[i-1\]\[j-1\]+s1\[i-1\]+s2\[j-1\]

再讨论，无论s1\[i-1\]和s2\[j-1\]是否相等，

（1）不要s1\[i-1\]，在s1\[0~i-2\]和 s2\[0~j-1\]中找删除字符串最小和

（2）不要s2\[j-1\], 在s1\[0~i-1\]和s2\[0~j-2\]中找删除字符串最小和

代码如下：

class Solution {
    public:
        int minimumDeleteSum(string s1, string s2) {
            int m = s1.length();
            int n =s2.length();
            int d[m+1][n+1];
            d[0][0] = 0;
            for(int i =1;i<=m;i++)
                d[i][0] = d[i-1][0]+s1[i-1];
            for(int j =1;j<=n;j++)
                d[0][j] = d[0][j-1]+s2[j-1];
            for(int i=1;i<=m;i++)
                for(int j=1;j<=n;j++)
                {
                    d[i][j] = min(d[i-1][j]+s1[i-1],d[i][j-1]+s2[j-1]);
                    if(s1[i-1]==s2[j-1])
                        d[i][j] = min(d[i][j],d[i-1][j-1]);
                    else
                        d[i][j] - min(d[i][j],d[i-1][j-1]+s1[i-1]+s2[j-1]);
                }
            return d[m][n];
        }
    };

转载于:https://www.cnblogs.com/jzcbest1016/p/9006850.html