Back to DSA

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

Related Problems

House RobbermediumClimbing StairseasyLongest Increasing SubsequencemediumWord BreakmediumUnique Pathsmedium
00:00
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        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];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}
Time complexityO(m * n)
Space complexityO(m * n)