LeetCode 72: Edit Distance Solution

Master LeetCode problem 72 (Edit Distance), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

72. Edit Distance

Medium

String Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can define a 2D array dp, where dp[i][j] represents the minimum number of operations required to convert the substring word1[0...i-1] to word2[0...j-1].

We can fill in the dp array iteratively, considering the following cases:

If the characters at index i in word1 and index j in word2 are the same, then no operation is needed, and dp[i][j] = dp[i-1][j-1].
If the characters are different, we have three options:
- Insert a character: dp[i][j] = dp[i][j-1] + 1
- Delete a character: dp[i][j] = dp[i-1][j] + 1
- Replace a character: dp[i][j] = dp[i-1][j-1] + 1

The final answer will be dp[word1.length()][word2.length()].

Solution Code

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];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else 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][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }

        return dp[m][n];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 72 (Edit Distance)?

This page provides optimized solutions for LeetCode problem 72 (Edit Distance) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 72 (Edit Distance)?

The time complexity for LeetCode 72 (Edit Distance) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 72 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 72 in Java, C++, or Python.

Back to LeetCode Solutions