Problem 583

Abstract / Summary

Given two strings, the task is to find the minimum number of deletions required to make them identical by removing characters from either string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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]
19 lines | 691 bytes | submitted August 15, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 66% (600k+ submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.38 | σ = 1.60

Complexity Analysis

Time: polynomial
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
37 links | 23 authors | 9 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

4 similar problems

Solved On The Same Day

30 solutions   August 15, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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