Build a 2D table where dp[i][j] holds the minimum operations to convert the first i characters of word1 into the first j characters of word2.

Edit Distance

hard

Acceptance: 43%

Dynamic Programming

Given two strings, determine the fewest single-character operations needed to transform the first string into the second. The permitted operations are inserting a character, removing a character, and substituting one character for another.

Examples

Example 1:

Input:word1 = "kitten", word2 = "sitting"

Output:3

Explanation: kitten -> sitten (substitute k with s) -> sittin (substitute e with i) -> sitting (insert g).

Example 2:

Input:word1 = "abc", word2 = "yabd"

Output:2

Explanation: abc -> yabc (insert y at front) -> yabd (substitute c with d).

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Edit Distance

Examples

Hints

Related Problems