What is the time complexity of Edit Distance?

The optimal solution has a time complexity of O(mn).

What data structures are used to solve Edit Distance?

This problem uses String, Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Edit Distance?

Insight 1: Dynamic Programming is essential because we can break down the problem into smaller overlapping subproblems. The optimal solution for transforming a prefix of word1 to a prefix of word2 can be built from the optimal solutions of smaller prefixes. Insight 2: The core idea is to consider the last characters of both strings. If they are the same, no operation is needed. If they are different, we consider insert, delete, and replace, and pick the operation that results in the minimum total operations.

Which companies ask LeetCode 72. Edit Distance in interviews?

This problem is frequently asked at Accenture, Adobe, Amazon, Apple, Arcesium and 21 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Edit Distance - LeetCode 72 Solution

Edit Distance - Complete Solution Guide

Edit Distance is LeetCode problem 72, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 (r

Detailed Explanation

The Edit Distance problem asks us to find the minimum number of operations (insert, delete, or replace) needed to transform one string (word1) into another string (word2). We are given two strings as input, and we need to return the smallest number of operations to make them identical. The constraints limit string lengths to a maximum of 500 characters consisting of lowercase English letters.

Solution Approach

The provided solution uses dynamic programming to solve the Edit Distance problem. It builds a 2D table `dp` where `dp[i][j]` represents the minimum number of operations to transform the first `i` characters of `word1` into the first `j` characters of `word2`. The algorithm iterates through the table, filling it based on the following logic: 1. **Base Cases:** The first row and column of the table are initialized. `dp[i][0] = i` because to convert the first `i` characters of `word1` to an empty string, we need `i` deletions. Similarly, `dp[0][j] = j` because to convert an empty string to the first `j` characters of `word2`, we need `j` insertions. 2. **Recursive Relation:** For each cell `dp[i][j]`, the algorithm checks if `word1[i-1]` is equal to `word2[j-1]`. If they are equal, it means no operation is needed, so `dp[i][j] = dp[i-1][j-1]`. If they are not equal, it considers three operations: insert, delete, and replace. The algorithm then takes the minimum of these three operations and adds 1 (for the operation itself) to get the value of `dp[i][j]`. 3. **Final Result:** The final answer, the minimum edit distance between `word1` and `word2`, is stored in `dp[m][n]`, where `m` is the length of `word1` and `n` is the length of `word2`.

Step-by-Step Algorithm

Step 1: Create a 2D DP table `dp` of size (m+1) x (n+1), where m and n are the lengths of word1 and word2 respectively.
Step 2: Initialize the first row and first column of `dp`. dp[i][0] = i for all i from 0 to m, and dp[0][j] = j for all j from 0 to n.
Step 3: Iterate through the remaining cells of `dp` (from i=1 to m and j=1 to n).
Step 4: For each cell dp[i][j], compare word1[i-1] and word2[j-1].
Step 5: If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1].
Step 6: If word1[i-1] != word2[j-1], then dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]). This considers insert, delete and replace operations, respectively.
Step 7: After filling the entire table, return dp[m][n].

Key Insights

Insight 1: Dynamic Programming is essential because we can break down the problem into smaller overlapping subproblems. The optimal solution for transforming a prefix of word1 to a prefix of word2 can be built from the optimal solutions of smaller prefixes.
Insight 2: The core idea is to consider the last characters of both strings. If they are the same, no operation is needed. If they are different, we consider insert, delete, and replace, and pick the operation that results in the minimum total operations.
Insight 3: We can use a 2D DP table `dp[i][j]` to store the minimum edit distance between the first `i` characters of `word1` and the first `j` characters of `word2`.

Complexity Analysis

Time Complexity: O(mn)

Space Complexity: O(mn)

Topics

This problem involves: String, Dynamic Programming.

Companies

Asked at: Accenture, Adobe, Amazon, Apple, Arcesium, Axon, Bloomberg, Cisco, DE Shaw, Deloitte, Flipkart, HashedIn, Infosys, LinkedIn, MakeMyTrip, Meta, Microsoft, Nielsen, Rubrik, Snap, Swiggy, TikTok, Visa, Yahoo, Zoho, tcs.

Edit Distance | LeetCode 72

Medium

String Dynamic Programming

Time: O(mn)Space: O(mn)

Solution Code

Available in:

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[i][j] will be the minimum number of operations to convert
        // word1's first i characters to word2's first j characters.
        int[][] dp = new int[m + 1][n + 1];

        // Initialize the DP table.
        // Base case: one of the strings is empty.
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // Fill the rest of the DP table.
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If the characters are the same, no new operation is needed.
                // The cost is the same as for the strings without these characters.
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // If characters are different, we consider three operations:
                    // 1. Insert: Convert word1[:i] to word2[:j-1] and insert word2[j-1].
                    //    Cost = dp[i][j-1] + 1
                    // 2. Delete: Convert word1[:i-1] to word2[:j] and delete word1[i-1].
                    //    Cost = dp[i-1][j] + 1
                    // 3. Replace: Convert word1[:i-1] to word2[:j-1] and replace word1[i-1].
                    //    Cost = dp[i-1][j-1] + 1
                    // We take the minimum of these three possibilities.
                    dp[i][j] = 1 + Math.min(dp[i][j - 1],      // Insert
                                       Math.min(dp[i - 1][j],      // Delete
                                       dp[i - 1][j - 1]));  // Replace
                }
        
            }
        }
        return dp[m][n];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 72: Edit Distance - Detailed explanation and solution approaches.

Topics

String Dynamic Programming

Companies

AccentureAdobeAmazonAppleArcesiumAxonBloombergCisco

Stats

Difficulty:Medium

Languages:4

Companies:26

Problem #:72

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Create a 2D DP table `dp` of size (m+1) x (n+1), where m and n are the lengths of word1 and word2 respectively.
2
Step 2: Initialize the first row and first column of `dp`. dp[i][0] = i for all i from 0 to m, and dp[0][j] = j for all j from 0 to n.
3
Step 3: Iterate through the remaining cells of `dp` (from i=1 to m and j=1 to n).
4
Step 4: For each cell dp[i][j], compare word1[i-1] and word2[j-1].
5
Step 5: If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1].
6
Step 6: If word1[i-1] != word2[j-1], then dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]). This considers insert, delete and replace operations, respectively.
7
Step 7: After filling the entire table, return dp[m][n].

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(mn)

💾

Space Complexity

O(mn)

📝

Why?

The time complexity is directly proportional to the number of cells in the DP table, which is (m+1) * (n+1). The space complexity is also determined by the size of the DP table.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Memoization (Top-Down Dynamic Programming)

Instead of building the DP table bottom-up, we can use a recursive function with memoization to solve the problem. This approach starts from the final goal and breaks it down into smaller subproblems, storing the results to avoid redundant calculations.

Time: O(mn)Space: O(mn) due to the memoization table and recursion stack.

Trade-offs: Memoization can be more intuitive for some, but it might have a larger constant factor due to function call overhead. Bottom-up DP is often slightly faster in practice.

Space Optimized DP

It is possible to optimize the space complexity to O(min(m, n)) by storing only the previous row of the DP table. Since each row only depends on the previous row, we don't need to store the entire table.

Time: O(mn)Space: O(min(m, n))

Trade-offs: This optimization reduces the space used at the cost of slightly increased code complexity. It's useful when memory is a constraint.

✨

Key Insights

1Insight 1: Dynamic Programming is essential because we can break down the problem into smaller overlapping subproblems. The optimal solution for transforming a prefix of word1 to a prefix of word2 can be built from the optimal solutions of smaller prefixes.
2Insight 2: The core idea is to consider the last characters of both strings. If they are the same, no operation is needed. If they are different, we consider insert, delete, and replace, and pick the operation that results in the minimum total operations.
3Insight 3: We can use a 2D DP table `dp[i][j]` to store the minimum edit distance between the first `i` characters of `word1` and the first `j` characters of `word2`.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: One of the strings is empty. The initialization of the DP table handles this case correctly. If `word1` is empty, the edit distance is the length of `word2` (all insertions). If `word2` is empty, the edit distance is the length of `word1` (all deletions).
Edge case 2: Both strings are empty. In this case, the edit distance is 0, which is also handled correctly by the initialization of the DP table (dp[0][0] = 0).

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Off-by-one errors when accessing characters in the strings. Remember that `dp[i][j]` corresponds to the first `i` characters of `word1` and the first `j` characters of `word2`, so the indices in the strings are `i-1` and `j-1`.

✗Common mistake 2: Forgetting to initialize the first row and column of the DP table correctly. These base cases are crucial for the algorithm to work.

✗Common mistake 3: Incorrectly applying the minimum operation calculation. Ensure that you're taking the minimum of insert, delete, and replace, and adding 1 to the result when the characters are different.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Spell checking. The edit distance can be used to suggest corrections for misspelled words. The closer the edit distance between a misspelled word and a dictionary word, the more likely it is that the dictionary word is the correct spelling.

🏦Real-world scenario 2: DNA sequencing. The edit distance can be used to measure the similarity between two DNA sequences. This is useful for identifying genetic mutations and tracing evolutionary relationships.

🎮Real-world scenario 3: Speech recognition. The edit distance is used to evaluate the accuracy of speech recognition systems by comparing the recognized text to the actual spoken words.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 12, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Edit Distance"?

For this medium-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?