LeetCode 0072 - Edit Distance
# Hints
- 区间DP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given two words word1
and word2
, find the minimum number of operations required to convert word1
to word2
.
You have the following operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
# 题意
给定两个字符串 word1
和 word2
,求将字符串 word1
转换为字符串 word2
所需的最少操作次数。操作有如下三种:
删除一个字符;
插入一个字符;
将一个字符改为另一个字符。
# 题解
为方便起见,我们设字符串下标从 起。
考虑动态规划,设 表示将 转化为 所需的最小操作次数。
状态转移方程:
$\begin{cases} dp[i][0] = i, &(initialize)\ dp[0][j] = j, &(initialize)\ dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1]), &(w_1[i] = w_2[j])\ dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1), &(w_1[i] \ne w_2[j]) \end{cases}$
其中从 转移表示删除字符,从 转移表示插入字符,从 转移表示 或是修改字符。
注意初始状态不是 ,将 转化为空串需要删除字符 次。 同理。
答案即为 。时间复杂度为 。
# AC代码
class Solution {
public:
int minDistance(const string & word1, const string & word2) {
// 初始化
int n = word1.length(), m = word2.length();
int dp[n + 1][m + 1];
// 递推
for (int i = 0; i <= n; i ++) {
dp[i][0] = i;
}
for (int j = 0; j <= m; j ++) {
dp[0][j] = j;
}
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
}
// 返回
return dp[n][m];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01