Skip to content

Autocorrect Distance

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Autocorrect Distance

An autocorrect engine measures how far a typed word word1 is from a dictionary word word2. One edit is an insertion, deletion, or substitution of a single character.

Return the minimum number of edits to turn word1 into word2.

def min_distance(word1, word2):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Dynamic Programming, 2D DP, Edit Distance, Strings

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What operations count as a single edit?
    • A: Inserting one character, deleting one character, or substituting one character for another. Each counts as exactly one edit.
  • Q: Do the edits have to be applied in a particular order or position?
    • A: No. We only care about the minimum total number of edits, not the sequence in which they are applied.
  • Q: What should the function return if one of the words is empty?
    • A: The length of the other word, since every character must be inserted (or deleted) one at a time.
HAPPY CASE
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse -> rorse (substitute 'h' with 'r'), rorse -> rose (delete 'r'), rose -> ros (delete 'e').

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: intention -> inention (delete 't'), inention -> enention (substitute 'i' with 'e'), enention -> exention (substitute 'n' with 'x'), exention -> exection (substitute 'n' with 'c'), exection -> execution (insert 'u').

EDGE CASE
Input: word1 = "", word2 = "abc"
Output: 3
Explanation: The typed word is empty, so all 3 characters of the dictionary word must be inserted.

Input: word1 = "same", word2 = "same"
Output: 0
Explanation: The words are identical, so no edits are needed.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For String Transformation Problems, we can consider the following approaches:

  • Dynamic Programming (2D DP): This is the classic Edit Distance (Levenshtein Distance) problem. The minimum edits for a pair of prefixes depends only on the answers for shorter prefixes, so we can build a 2D table of subproblem answers.
  • Recursion with Memoization: Compare the words character by character from the front, branching on insert/delete/substitute and caching results — the top-down version of the same DP.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Define a 2D table where dp[i][j] is the minimum number of edits to turn the first i characters of word1 into the first j characters of word2. If the current characters match, no edit is needed and we carry over the diagonal value. Otherwise, we take 1 plus the best of the three possible edits: substitution (diagonal), deletion (up), or insertion (left). The answer is the bottom-right cell.

1) Let m = len(word1) and n = len(word2). Create a (m+1) x (n+1) table `dp`.
2) Fill in the base cases:
   a) dp[i][0] = i for every i (turn a prefix of word1 into "" by deleting i characters).
   b) dp[0][j] = j for every j (turn "" into a prefix of word2 by inserting j characters).
3) For each i from 1 to m and each j from 1 to n:
   a) If word1[i-1] == word2[j-1], set dp[i][j] = dp[i-1][j-1] (no edit needed).
   b) Otherwise, set dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
      corresponding to substitution, deletion, and insertion.
4) Return dp[m][n].

⚠️ Common Mistakes

  • Forgetting the base cases for the empty string (row 0 and column 0), which anchor the whole table.
  • Mixing up the indices: dp[i][j] describes prefixes of length i and j, so the characters being compared are word1[i-1] and word2[j-1].
  • Adding 1 to the diagonal even when the characters match, which overcounts edits.
  • Confusing which neighbor represents which operation (diagonal = substitution, up = deletion, left = insertion).

4: I-mplement

Implement the code to solve the algorithm.

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    # dp[i][j] = min edits to turn word1[:i] into word2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: transforming to/from an empty string
    for i in range(m + 1):
        dp[i][0] = i  # delete all i characters
    for j in range(n + 1):
        dp[0][j] = j  # insert all j characters

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # characters match, no edit
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # substitution
                    dp[i - 1][j],      # deletion from word1
                    dp[i][j - 1],      # insertion into word1
                )

    return dp[m][n]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: word1 = "horse", word2 = "ros"

    • The table is 6 x 4. Row 0 fills as 0,1,2,3 and column 0 fills as 0,1,2,3,4,5.
    • At i=3, j=2 ('r' in "hor" vs 'o' — mismatch) and the surrounding cells, the table records that "hor" -> "ro" costs 2.
    • The bottom-right cell dp[5][3] resolves to 3: substitute 'h'->'r', delete 'r', delete 'e'.
    • Output: 3

  • Input: word1 = "intention", word2 = "execution"

    • The table is 10 x 10. The shared suffix "tion" makes the last four diagonal steps free.
    • dp[9][9] resolves to 5: delete 't', substitute 'i'->'e', substitute 'n'->'x', substitute 'n'->'c', insert 'u'.
    • Output: 5

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

    • Only the base-case row applies: dp[0][3] = 3.
    • Output: 3

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume M is the length of word1 and N is the length of word2.

  • Time Complexity: O(M * N) because we fill in every cell of the (M+1) x (N+1) table exactly once, doing constant work per cell.
  • Space Complexity: O(M * N) for the DP table. Since each row depends only on the previous row, this can be reduced to O(min(M, N)) by keeping just two rows.

Clone this wiki locally