【必备算法】动态规划：LeetCode题（五）1143. 最长公共子序列，72. 编辑距离

我不是女神ヾ 2022-11-06 02:56 7阅读 0赞

## [1143. 最长公共子序列²][1143.] ##

给定两个字符串 `text1` 和 `text2`，返回这两个字符串的最长公共子序列的长度。

一个字符串的 *子序列* 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。  
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

**示例 1:**

输入：text1 = "abcde", text2 = "ace" 
    输出：3  
    解释：最长公共子序列是 "ace"，它的长度为 3。

**示例 2:**

输入：text1 = "abc", text2 = "abc"
    输出：3
    解释：最长公共子序列是 "abc"，它的长度为 3。

**示例 3:**

输入：text1 = "abc", text2 = "def"
    输出：0
    解释：两个字符串没有公共子序列，返回 0。

**提示:**

*  `1 <= text1.length <= 1000`
 *  `1 <= text2.length <= 1000`
 *  输入的字符串只含有小写英文字符。

### 解法：动态规划 ###

*  思路：分解模型&&重复子问题（==>求所有中间串的最长子序列）
    
     *  状态定义：`d[i][j]`。s1.sub(1,i)与s2.sub(1,j)的最长子序列（从1开始是要包含空串情况）
     *  初始状态：`d[i][0]=0, d[0][j]=0`。任意一个串长度为0，则无公共子序列（注：由于数组默认初始值为0，所以不用再显式声明）
     *  状态方程：`d[i][j]= s1.charAt(i) == s2.charAt(j) ? d[i-1][j-1] + 1 : max(d[i-1][j],[i][j-1])`
        
         *  若char(i)=char(j)，则长度+1
         *  若char(i)!=char(j)，则必有一个字符或两个字符（该情况已包含）都不在子序列中
     *  最终状态：`d[s1.len][s2.len]`
 *  复杂度：
    
     *  Time：O(n \* m)
     *  Space：O(n \* m)

public int longestCommonSubsequence(String text1, String text2) {
        
            // 状态数组
            int[][] d = new int[text1.length() + 1][text2.length() + 1];
    
            // 状态初始：d[i][0]=0, d[0][j]=0。不用再显式声明。
            
            // 状态递推
            for (int i = 1; i <= text1.length(); i++) 
                for (int j = 1; j <= text2.length(); j++) 
                    if (text1.charAt(i - 1) == text2.charAt(j - 1)) 
                        d[i][j] = d[i - 1][j - 1] + 1;
                    else
                        d[i][j] = Math.max(d[i - 1][j], d[i][j - 1]);
    
            // 最终状态：d[s1.len][s2.len]
            return d[text1.length()][text2.length()];
        }

## [72. 编辑距离³][72.] ##

给你两个单词 *word1* 和 *word2*，请你计算出将 *word1* 转换成 *word2* 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1.  插入一个字符
2.  删除一个字符
3.  替换一个字符

**示例 1：**

输入：word1 = "horse", word2 = "ros"
    输出：3
    解释：
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')

**示例 2：**

输入：word1 = "intention", word2 = "execution"
    输出：5
    解释：
    intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')

### 解法：动态规划 ###

*  思路：分解模型&&重复子问题（==>求word1变成word2中间串的最小编辑距离）
    
     *  状态数组：`d[i][j]`。word1.sub(0,i) 与 word2.sub(0,j) 的最小编辑距离，也可以理解成word1的前i个字符和word2的前j个字符已经相同了
     *  初始状态：`d[i][0] = i`,`d[0][j] = j`。任意一个word为空则编辑距离等于另一个word长度
     *  状态数组：`d[i][j] = w1.charAt(i-1) == w2.charAt(j-1) ? d[i-1][j-1] : min(d[i-1][j-1],d[i-1][j],d[i][j-1]) +1`。若两个串最后一个字母相同，直接不管，否则换/删/增，再操作数+1：
        
         *  改：`d[i][j] = d[i-1][j-1] + 1`。将word1的当前字符(i)改到与word2(j)相同，所以i，j都减一
         *  删：`d[i][j] = d[i-1][j] + 1`。将word1的当前字符(i)删除，所以只有 i 减一
         *  增：`d[i][j] = d[i][j-1] + 1`。将word1加上当前字符，所以只有 j 减一
     *  最终状态： `d[w1.len-1][w2.len-1]`。
 *  复杂度：
    
     *  Time：O(m\*n)
     *  Space：O(m\*n)

class Solution {
        
    
        public int minDistance(String word1, String word2) {
        
            int m = word1.length() + 1, n = word2.length() + 1; // +1是状态还要保存空串情况
            // 状态数组
            int[][] d = new int[m][n];
            
            // 初始状态
            for (int i = 0; i < m; i++) d[i][0] = i;
            for (int j = 0; j < n; j++) d[0][j] = j;
            
            // 状态递推。递推过程本质就是一个填表的过程！
            for (int i = 1; i < m; i++) 
                for (int j =1; j < n; j++) 
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) 
                        d[i][j] = d[i - 1][j - 1];
                    else
                        d[i][j] = min(d[i - 1][j - 1],d[i - 1][j], d[i][j - 1]) + 1;
                        
            // 4.最终状态：d[w1.len-1][w2.len-1]
            return d[m - 1][n - 1];
        }
    	
    	// 辅助函数，用来求三个数的最小值
        private int min(int a, int b, int c) {
        
            return Math.min(Math.min(a, b), c);
        }
    }

[1143.]: https://leetcode-cn.com/problems/longest-common-subsequence/
[72.]: https://leetcode-cn.com/problems/edit-distance/