Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Medium

Edit Distance

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

Examples

Input:word1 = "horse", word2 = "ros"
Output:3
horse -> rorse (replace 'h' with 'r') rorse -> rose (delete 'r') rose -> ros (delete 'e')
Input:word1 = "intention", word2 = "execution"
Output:5
intention -> inention (delete '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.

Dynamic Programming (Bottom-Up)

Approach

We use a 2D DP table `dp` where `dp[i][j]` represents the edit distance between `word1[0...i-1]` and `word2[0...j-1]`. Base cases: converting an empty string to a string of length `j` takes `j` insertions. Converting a string of length `i` to an empty string takes `i` deletions. For each character, if `word1[i-1] == word2[j-1]`, no operation is needed, so `dp[i][j] = dp[i-1][j-1]`. If they are different, we can either: 1. Insert: `dp[i][j-1] + 1` 2. Delete: `dp[i-1][j] + 1` 3. Replace: `dp[i-1][j-1] + 1` We take the minimum of these three options.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(m * n)

Time and space complexity are O(m * n) where m and n are the lengths of the two strings. Space can be optimized to O(min(m, n)) as we only need the previous row to compute the current row.

Solution.java
class Solution {    public int minDistance(String word1, String word2) {        int m = word1.length();        int n = word2.length();        int[][] dp = new int[m + 1][n + 1];                // Base cases        for (int i = 0; i <= m; i++) {            dp[i][0] = i; // Delete all characters        }        for (int j = 0; j <= n; j++) {            dp[0][j] = j; // Insert all characters        }                // DP transitions        for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                    dp[i][j] = dp[i - 1][j - 1]; // No operation                } else {                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // Replace                                  Math.min(dp[i - 1][j],      // Delete                                           dp[i][j - 1]));    // Insert                }            }        }                return dp[m][n];    }}