Skip to content

72. Edit Distance

DifficultyMedium

Description

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three 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')

 

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

Solutions

Solution 1: Dynamic Programming

Thinking

The first idea is recursion: at each position of \(word1\) try insert, delete, or replace, then take the best. Correct, but exponential. \(m,n \le 500\) needs a polynomial.

The bottleneck is overlapping subproblems — converting prefix \(i\) into prefix \(j\) is solved many times. Let \(f[i][j]\) be that minimum. Equal last characters inherit the diagonal; otherwise the three operations map to three neighbors, take \(\min\) plus one. Empty-string borders are delete-all / insert-all. The answer is \(f[m][n]\).

We define \(f[i][j]\) as the minimum number of operations to convert \(word1\) of length \(i\) to \(word2\) of length \(j\). \(f[i][0] = i\), \(f[0][j] = j\), \(i \in [1, m], j \in [0, n]\).

We consider \(f[i][j]\):

  • If \(word1[i - 1] = word2[j - 1]\), then we only need to consider the minimum number of operations to convert \(word1\) of length \(i - 1\) to \(word2\) of length \(j - 1\), so \(f[i][j] = f[i - 1][j - 1]\);
  • Otherwise, we can consider insert, delete, and replace operations, then \(f[i][j] = \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1\).

Finally, we can get the state transition equation:

\[ f[i][j] = \begin{cases} i, & \textit{if } j = 0 \\ j, & \textit{if } i = 0 \\ f[i - 1][j - 1], & \textit{if } word1[i - 1] = word2[j - 1] \\ \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1, & \textit{otherwise} \end{cases} \]

Finally, we return \(f[m][n]\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). \(m\) and \(n\) are the lengths of \(word1\) and \(word2\) respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for j in range(1, n + 1):
            f[0][j] = j
        for i, a in enumerate(word1, 1):
            f[i][0] = i
            for j, b in enumerate(word2, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1
        return f[m][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] f = new int[m + 1][n + 1];
        for (int j = 1; j <= n; ++j) {
            f[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            f[i][0] = i;
            for (int j = 1; j <= n; ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) + 1;
                }
            }
        }
        return f[m][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        int f[m + 1][n + 1];
        for (int j = 0; j <= n; ++j) {
            f[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            f[i][0] = i;
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = min({f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) + 1;
                }
            }
        }
        return f[m][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    for j := 1; j <= n; j++ {
        f[0][j] = j
    }
    for i := 1; i <= m; i++ {
        f[i][0] = i
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                f[i][j] = f[i-1][j-1]
            } else {
                f[i][j] = min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1
            }
        }
    }
    return f[m][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function minDistance(word1: string, word2: string): number {
    const m = word1.length;
    const n = word2.length;
    const f: number[][] = Array(m + 1)
        .fill(0)
        .map(() => Array(n + 1).fill(0));
    for (let j = 1; j <= n; ++j) {
        f[0][j] = j;
    }
    for (let i = 1; i <= m; ++i) {
        f[i][0] = i;
        for (let j = 1; j <= n; ++j) {
            if (word1[i - 1] === word2[j - 1]) {
                f[i][j] = f[i - 1][j - 1];
            } else {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
            }
        }
    }
    return f[m][n];
}

 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
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const f = Array(m + 1)
        .fill(0)
        .map(() => Array(n + 1).fill(0));
    for (let j = 1; j <= n; ++j) {
        f[0][j] = j;
    }
    for (let i = 1; i <= m; ++i) {
        f[i][0] = i;
        for (let j = 1; j <= n; ++j) {
            if (word1[i - 1] === word2[j - 1]) {
                f[i][j] = f[i - 1][j - 1];
            } else {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
            }
        }
    }
    return f[m][n];
};

Comments