6.7 字符串编辑

# 6.7 字符串编辑

## [72. Edit Distance](https://leetcode.com/problems/edit-distance/)

### 题目描述

给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可以将两个字符串变成相同。

### 输入输出样例

输入是两个字符串，输出是一个整数，表示最少的步骤。

```
Input: word1 = "horse", word2 = "ros"
Output: 3
```

在这个样例中，一种最优编辑方法是 horse -> rorse -> rose -> ros。

### 题解

类似于题目 1143，我们使用一个二维数组 dp[i][j]，表示将第一个字符串到位置 i 为止，和第二个字符串到位置 j 为止，最多需要几步编辑。当第 i 位和第 j 位对应的字符相同时，dp[i][j] 等于 dp[i-1][j-1]；当二者对应的字符不同时，修改的消耗是 dp[i-1][j-1]+1，插入 i 位置/删除 j 位置的消耗是 dp[i][j-1] + 1，插入 j 位置/删除 i 位置的消耗是 dp[i-1][j] + 1。

```py
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    dp[i][j] = i + j
                else:
                    dp[i][j] = min(
                        dp[i - 1][j - 1] + int(word1[i - 1] != word2[j - 1]),
                        dp[i][j - 1] + 1,
                        dp[i - 1][j] + 1,
                    )
        return dp[m][n]

```

## [650. 2 Keys Keyboard](https://leetcode.com/problems/2-keys-keyboard/)

### 题目描述

给定一个字母 A，已知你可以每次选择复制全部字符，或者粘贴之前复制的字符，求最少需要几次操作可以把字符串延展到指定长度。

### 输入输出样例

输入是一个正整数，代表指定长度；输出是一个整数，表示最少操作次数。

```
Input: 3
Output: 3
```

在这个样例中，一种最优的操作方法是先复制一次，再粘贴两次。

### 题解
dp[i]表示的是得到i个A所需要的最小次数
接下来就是循环，如果 i%j==0 :说明i个A可以由m个j得到
那么接下来就是需要1次copy，以及 $$(i//j)-1$$ 次paste
表达式为 $$dp[i]=min(dp[i],dp[j]+1+i//j−1)$$
即为 $$dp[i]=min(dp[i],dp[j]+i//j)$$
```py
class Solution:
    def minSteps(self, n: int) -> int:
        dp = [inf] * (n + 1)
        dp[1] = 0
        for i in range(2, n + 1):
            for j in range(1, i):
                if i % j == 0:
                    dp[i] = min(dp[i], dp[j] + i // j)
        return dp[n]
```