Python 0583.py
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# edit distance
cost = [ [ 0 for i in range(len(word2) + 1)] for j in range(len(word1) + 1) ]
for i in range(len(word1) + 1):
cost[len(word1) - i][len(word2)] = i
for j in range(len(word2) + 1):
cost[len(word1)][len(word2) - j] = j
for i in range(len(word1) - 1, -1, -1):
for j in range(len(word2) - 1, -1, -1):
if word1[i] == word2[j]:
cost[i][j] = cost[i+1][j+1]
else:
cost[i][j] = 1 + min(cost[i+1][j], cost[i][j+1])
return cost[0][0]
Difficulty
and has an acceptance rate of about 66% (600k+ submissions).
Typical patterns to solve this problem:
- Dynamic Programming
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation computes the minimum number of single-character operations required to transform one string into another, commonly known as the edit distance or Levenshtein distance. It adopts a dynamic-programming approach that fills a two-dimensional table from the bottom-right corner toward the top-left, thereby ensuring that every sub-problem is solved before it is needed by larger sub-problems. The final answer is obtained from the table entry that corresponds to the full strings.
Key Steps
Table Allocation
The algorithm begins by allocating a matrix named cost whose dimensions are one greater than the lengths of the two input strings. This extra row and column serve as base cases for the recursion.
cost = [ [ 0 for i in range(len(word2) + 1)] for j in range(len(word1) + 1) ]
Initialization of the Last Column
The last column of the matrix represents the cost of deleting the remaining characters of word1 when word2 is already exhausted. The loop walks backward through the rows, assigning the appropriate deletion count.
for i in range(len(word1) + 1):
cost[len(word1) - i][len(word2)] = i
Initialization of the Last Row
Similarly, the last row captures the cost of inserting the remaining characters of word2 when word1 is exhausted. The loop iterates backward through the columns.
for j in range(len(word2) + 1):
cost[len(word1)][len(word2) - j] = j
Bottom-Up Filling of the Table
The core of the algorithm iterates over the matrix in reverse order, excluding the already initialized border cells. For each pair of positions (i, j), the algorithm checks whether the characters match. If they do, the cost is inherited from the diagonal successor; otherwise, the cost is one plus the minimum of the costs of deleting a character from word1 or inserting a character from word2.
for i in range(len(word1) - 1, -1, -1):
for j in range(len(word2) - 1, -1, -1):
if word1[i] == word2[j]:
cost[i][j] = cost[i+1][j+1]
else:
cost[i][j] = 1 + min(cost[i+1][j], cost[i][j+1])
Result Extraction
After the matrix is fully populated, the entry at the top-left corner holds the minimum edit distance for the complete strings.
return cost[0][0]
Edge Cases Handled
When either input string is empty, the initialization of the last row and column directly yields the correct distance, which equals the length of the non-empty string. The loops that fill the interior of the matrix gracefully skip execution when one of the dimensions is zero, leaving the border values untouched and accurate.
If the two strings are identical, the character comparison inside the nested loops always succeeds, causing the algorithm to propagate zero cost from the bottom-right corner to the top-left corner. Consequently, the function returns zero, reflecting that no operations are needed.
When one string is a prefix of the other, the algorithm correctly accumulates the cost of the extra trailing characters through the border initialization, and the interior loops simply copy those values forward, yielding the expected distance equal to the length difference.
Performance Optimizations Observed
The implementation avoids recomputation by storing intermediate results in the cost matrix, guaranteeing that each sub-problem is solved exactly once. By iterating from the end of the strings toward the beginning, the algorithm ensures that the values required for each cell are already available, eliminating the need for recursive calls or additional data structures.
The explicit initialization of the last row and column reduces the number of conditional checks inside the main double loop, as the algorithm never needs to verify out-of-bounds indices during the core computation. This design choice streamlines the inner loop body to a simple character comparison followed by a constant-time selection of the minimum of two pre-computed values.
Memory allocation is performed once at the start, and the matrix is accessed using direct indexing, which benefits from contiguous storage in Python’s list-of-lists representation. The use of min with two arguments avoids the overhead of constructing temporary collections, keeping the inner loop lightweight.
Overall, the code exhibits a clear separation between initialization and computation phases, allowing the Python interpreter to optimize each phase independently and resulting in a solution that runs efficiently for typical input sizes.
ELI5 - Simplified Explanation
Imagine two messy toy boxes filled with different blocks. This code plays a game to figure out the easiest way to turn one set of blocks into another by changing them, adding new ones, or taking away the extra ones that do not fit.
To keep track of the moves, it builds a big grid like a treasure map. Each spot in the grid remembers how many more steps are needed to make the ends of the words match up. It starts from the very end of the words and works its way back to the beginning.
If the letters at the current spot match, it just moves on because those blocks are already perfect. If the letters are different, it looks at the neighboring spots in the grid. It picks the path that needs the smallest amount of changes to fix the mess. By filling in all the squares in the grid, it eventually finds the very best total number of moves needed to turn one word into the other.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | Java | Rust | Go | TS | ||||
| LeetcodeHelp | C++ | Python | Java | |||||||
| Progiez | C++ | Python | Java | |||||||
| github | black-shadows | C++ | ||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| fengvyi | C++ | |||||||||
| fpdjsns | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| martianoff | Scala | |||||||||
| ruoru | Rust | |||||||||
| sonugiri1043 | C++ | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| wisdompeak | C++ | |||||||||
| zfang399 | C++ | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| Progiez | C++, Java, Python | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| fengvyi | C++ | |||||||||
| fpdjsns | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| martianoff | Scala | |||||||||
| ruoru | Rust | |||||||||
| sonugiri1043 | C++ | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| wisdompeak | C++ | |||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 72: Edit Distance
- problem 712: Minimum ASCII Delete Sum for Two Strings
- problem 1143: Longest Common Subsequence
- problem 2937: Make Three Strings Equal
Solved On The Same Day
- problem 112: Path Sum
- problem 409: Longest Palindrome
- problem 645: Set Mismatch
- problem 717: 1-bit and 2-bit Characters
- problem 2535: Difference Between Element Sum and Digit Sum of an Array
- problem 16: 3Sum Closest
- problem 24: Swap Nodes in Pairs
- problem 113: Path Sum II
- problem 114: Flatten Binary Tree to Linked List
- problem 116: Populating Next Right Pointers in Each Node
- problem 129: Sum Root to Leaf Numbers
- problem 131: Palindrome Partitioning
- problem 137: Single Number II
- problem 162: Find Peak Element
- problem 165: Compare Version Numbers
- problem 172: Factorial Trailing Zeroes
- problem 201: Bitwise AND of Numbers Range
- problem 204: Count Primes
- problem 402: Remove K Digits
- problem 430: Flatten a Multilevel Doubly Linked List
- problem 451: Sort Characters By Frequency
- problem 539: Minimum Time Difference
- problem 633: Sum of Square Numbers
- problem 648: Replace Words
- problem 650: 2 Keys Keyboard
- problem 670: Maximum Swap
- problem 786: K-th Smallest Prime Fraction
- problem 2507: Smallest Value After Replacing With Sum of Prime Factors
- problem 2523: Closest Prime Numbers in Range
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality