Skip to main content
Talentd

Edit Distance - Solution & Explanation

MediumStringDynamic Programming18 min readAsked at: Amazon, Microsoft, Apple +21
Practice this problem

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 (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

 

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

Approach Overview

Problem Overview: Given two strings word1 and word2, compute the minimum number of operations required to convert one into the other. Allowed operations are insert, delete, and replace a character. The task is essentially measuring how different the two strings are using the fewest edits.

Approach 1: Recursive with Memoization (O(m*n) time, O(m*n) space)

This approach models the problem directly with recursion. At any index i in word1 and j in word2, you compare characters and decide which operation to apply. If the characters match, move both pointers forward with no cost. Otherwise try three choices: insert (advance j), delete (advance i), or replace (advance both). Each recursive call returns the minimum cost from that state.

Without caching, the recursion explores the same subproblems repeatedly, leading to exponential time. Memoization stores results for each (i, j) pair so every state is computed once. The number of states is m * n, where m and n are string lengths. This technique demonstrates the optimal substructure clearly and is a natural application of recursion combined with caching.

Approach 2: Dynamic Programming (Tabulation) (O(m*n) time, O(m*n) space)

The dynamic programming solution converts the recursive idea into a bottom-up table. Create a 2D DP array where dp[i][j] represents the minimum edits needed to convert the first i characters of word1 into the first j characters of word2. Initialize the first row and column because converting to or from an empty string requires only insertions or deletions.

For each cell, compare the current characters from the two strings. If they match, copy the value from dp[i-1][j-1]. If they differ, compute the minimum of three operations: insert (dp[i][j-1]), delete (dp[i-1][j]), or replace (dp[i-1][j-1]). Add one to represent the operation cost. Iterating through the matrix fills all subproblems efficiently.

This is the classic edit distance DP formulation and commonly appears when working with string transformation problems and dynamic programming. The DP table guarantees each subproblem is solved exactly once, producing an optimal solution in quadratic time.

Recommended for interviews: Interviewers typically expect the dynamic programming solution. Starting with the recursive idea shows you understand the decision process behind each edit operation. Converting it into a DP table demonstrates that you can optimize overlapping subproblems and reason about state transitions—skills that are core to dynamic programming interviews.

Approach 1: Dynamic Programming Approach

This approach uses a 2D array to store the edit distances between all prefixes of both strings. By building solutions for smaller subproblems, we can efficiently calculate the solution for the entire problem.

We define dp[i][j] as the edit distance between the first i characters of word1 and the first j characters of word2. The recursion is based on comparing the last characters of the current substrings. If they are the same, the edit distance is the same as dp[i-1][j-1], otherwise, we add 1 (to account for an edit operation) and consider the minimum edit distance found after each possible operation: insertion, deletion, or replacement.

This Python implementation uses dynamic programming. We start with initializing a table where each cell dp[i][j] represents the edit distance between the first i characters of word1 and the first j characters of word2.

The base cases are filled as follows: dp[i][0] = i (deleting all i characters of word1 to match an empty word2) and dp[0][j] = j (inserting all j characters of word2 into an empty word1).

We then populate the table by computing the cost of each edit operation and choosing the one with the minimum cost.

Code

PythonJavaScriptC

Python

JavaScript

C

Complexity

Time Complexity: O(m * n) where m and n are the lengths of word1 and word2 respectively, as we compute values for each combination of indices.

Space Complexity: O(m * n) for storing the dp table.

Try this approach in the editor →

Approach 2: Recursive Approach with Memoization

This approach uses recursive calls with memoization to effectively reduce the factors of redundant subproblem calculations. We use a hash map or an array to store results of previously encountered subproblems to avoid recalculating them, subsequently turning the recursive depth-first search into a memoized search.

This Java solution implements a top-down recursion with memoization. The primary operation function 'helper' recursively solves the edit distance problem by considering character matches and operations separately.

Memoization is achieved by storing results of subproblems in a HashMap, uniquely keyed by the indices of remaining substrings.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(m * n) where m and n are lengths of word1 and word2. Each subproblem is computed once.

Space Complexity: O(m * n) for memoization storage plus recursion call stack space.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] as the minimum number of operations to convert word1 of length i to word2 of length j. f[i][0] = i, f[0][j] = j, i \in [1, m], j \in [0, n].

We consider f[i][j]:

  • If word1[i - 1] = word2[j - 1], then we only need to consider the minimum number of operations to convert word1 of length i - 1 to word2 of length j - 1, so f[i][j] = f[i - 1][j - 1];
  • Otherwise, we can consider insert, delete, and replace operations, then f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1.

Finally, we can get the state transition equation:

$ f[i][j] = \begin{cases} i, & if j = 0 \ j, & if i = 0 \ f[i - 1][j - 1], & if word1[i - 1] = word2[j - 1] \ min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1, & otherwise \end{cases}

Finally, we return f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). m and n are the lengths of word1 and word2$ respectively.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(m * n) where m and n are the lengths of word1 and word2 respectively, as we compute values for each combination of indices.

Space Complexity: O(m * n) for storing the dp table.

Recursive Approach with Memoization

Time Complexity: O(m * n) where m and n are lengths of word1 and word2. Each subproblem is computed once.

Space Complexity: O(m * n) for memoization storage plus recursion call stack space.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(m*n)O(m*n)Good for understanding the problem structure and explaining recursive choices in interviews
Dynamic Programming (2D Table)O(m*n)O(m*n)Standard interview solution; clear state transition and easy to implement
Space-Optimized DPO(m*n)O(min(m,n))When memory usage matters; uses rolling rows instead of the full DP matrix

Video Solution

Edit Distance - Dynamic Programming - Leetcode 72 - Python • NeetCode • 223,956 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Edit Distance easy or hard?
Edit Distance is generally considered a medium dynamic programming problem. The challenge is defining the correct state transition between insert, delete, and replace operations. Once the DP state dp[i][j] is understood, the implementation becomes straightforward.
How to solve Edit Distance in O(n)?
Edit Distance cannot be solved in O(n) time for general inputs because every character pair may affect the result. The optimal algorithm requires O(m*n) comparisons. Space can be reduced to O(n) by keeping only the previous and current DP rows instead of storing the entire matrix.
What is the best approach for Edit Distance?
Dynamic programming is the standard solution. Build a 2D DP table where dp[i][j] represents the minimum edits required to convert the first i characters of word1 into the first j characters of word2. Each state checks insert, delete, and replace operations. The algorithm runs in O(m*n) time and O(m*n) space.
Is Edit Distance asked at Google Amazon Meta?
Edit Distance is a classic dynamic programming problem frequently asked in technical interviews at companies like Google, Amazon, and Meta. Variations appear in system design and NLP-related interview questions where string similarity or transformation cost is relevant.
What data structure is used in Edit Distance?
The core data structure is a 2D dynamic programming array that stores the edit cost for each substring pair. Memoized recursion uses a hash map or 2D array for caching. The structure tracks overlapping subproblems efficiently during string comparison.
What is the time complexity of Edit Distance?
The optimal dynamic programming solution runs in O(m*n) time where m and n are the lengths of the two strings. Every pair of indices (i, j) is computed once. Space complexity is typically O(m*n), although it can be reduced to O(min(m,n)) using a rolling array optimization.
Edit Distance Python or Java solution approach?
Both Python and Java implementations follow the same DP table strategy. Initialize a matrix of size (m+1) by (n+1), fill base cases for empty strings, then iterate through characters updating dp[i][j] based on insert, delete, and replace costs. The final answer appears at dp[m][n].

Ready to solve this problem?

Practice Edit Distance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Delete Operation for Two Strings

Next

Longest Palindrome After Substring Concatenation II