{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Edit Distance – Solution & Complexity

Interview solutions
/
Edit Distance

Solution Walkthrough

  1. Step 1: Define the Subproblem

    • Let dp[i][j] be the minimum edits needed to convert the first i characters of word1 into the first j characters of word2.
    • Empty prefixes give the base cases: converting to or from an empty string requires only insertions or deletions.
    • The final answer is the value for the full lengths of both words.

  2. Step 2: Choose Between the Three Operations

    • If the current characters match, no new edit is needed and we reuse the diagonal subproblem.
    • Otherwise, try the cheapest of insert, delete, or replace.
    • Each operation costs one edit plus the best smaller subproblem.
    if word1[i - 1] == word2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]
else:
    dp[i][j] = 1 + min(
        dp[i][j - 1],      # insert
        dp[i - 1][j],      # delete
        dp[i - 1][j - 1],  # replace
    )

  3. Step 3: Optimize Space with One Row

    • The recurrence only needs the previous row and the current row.
    • Store distances for converting the processed prefix of word1 to every prefix of word2.
    • For each character in word1, build a fresh current row from previous.
    previous = list(range(len(word2) + 1))
for i in range(1, len(word1) + 1):
    current = [i] + [0] * len(word2)
    # Fill current[j] using previous and current[j - 1].

  4. Step 4: Fill Rows Left to Right

    • current[j - 1] represents insertion, because the target prefix is one character shorter.
    • previous[j] represents deletion, because the source prefix is one character shorter.
    • previous[j - 1] represents replacement or a character match.
    for j in range(1, len(word2) + 1):
    if word1[i - 1] == word2[j - 1]:
        current[j] = previous[j - 1]
    else:
        current[j] = 1 + min(current[j - 1], previous[j], previous[j - 1])

  5. Step 5: Final Complete Solution

    • This dynamic programming solution handles empty strings through the initialized base row and first column.
    • It keeps only one previous row, so memory is linear in the length of word2.
    • Time complexity is O(mn), and extra space complexity is O(n).
    def min_distance(word1: str, word2: str) -> int:
    previous = list(range(len(word2) + 1))

    for i in range(1, len(word1) + 1):
        current = [i] + [0] * len(word2)
        for j in range(1, len(word2) + 1):
            if word1[i - 1] == word2[j - 1]:
                current[j] = previous[j - 1]
            else:
                current[j] = 1 + min(
                    current[j - 1],
                    previous[j],
                    previous[j - 1],
                )
        previous = current

    return previous[-1]

FAQ

See also

Practice Edit Distance online (run code in the browser)Decode Ways solution (medium)Longest Common Subsequence solution (medium)Longest Palindromic Substring solution (medium)Longest Valid Parentheses solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?