leetcode-72 Edit Distance

72. Edit Distance

Description

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

1
2
3
4
5
6
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

1
2
3
4
5
6
7
8
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')

Analyse

计算两个字符串的编辑距离

递归解法

这个代码结果应该是正确的，但是内存超了，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int min(int a, int b, int c) {
        int min = a;
        min = min < b ? min : b;
        min = min < c ? min : c;
        return min;
    }
    int dp(string word1, string word2, int i, int j) {
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;

        if (word1[i] == word2[j]) {
            return dp(word1, word2, i - 1, j - 1);
        } else {
            return min(dp(word1, word2, i - 1, j - 1),
                      dp(word1, word2, i, j - 1),
                      dp(word1, word2, i - 1, j)) + 1;
        }
    }

    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();

        return dp(word1, word2, len1 - 1, len2 - 1);
    }
};

动态规划解法

  • 备忘录

  • 算dp数组