Implement Edit Distance (Levenshtein Distance) using Dynamic Programming in Python

[srijani006]

Edit Distance (Levenshtein Distance) — Dynamic Programming

Overview

The Edit Distance (also known as Levenshtein Distance) is a classic Dynamic Programming problem that measures how dissimilar two strings are by counting the minimum number of operations required to transform one string into another.

The allowed operations are:

1. Insertion of a character
2. Deletion of a character
3. Substitution of one character for another

This algorithm is widely used in spell checkers, DNA sequencing, and natural language processing (NLP) applications.

---

Algorithm Explanation

We use a Bottom-Up Dynamic Programming approach.

Let dp[i][j] represent the minimum number of operations required to convert
the first i characters of word1 into the first j characters of word2.

Recurrence Relation:

If word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # Characters match, no operation
Else:
dp[i][j] = 1 + min(
dp[i-1][j], # Deletion
dp[i][j-1], # Insertion
dp[i-1][j-1] # Substitution
)

Base Conditions:

• dp[0][j] = j → Convert empty string to word2[:j] (j insertions)
• dp[i][0] = i → Convert word1[:i] to empty string (i deletions)

---

Time and Space Complexity

Complexity	Value
Time	O(m × n)
Space	O(m × n)

where m and n are the lengths of the two strings.

---

Example

Input:
word1 = "kitten"
word2 = "sitting"

Output:
3

Explanation:
kitten → sitten (substitution of 's' for 'k')
sitten → sittin (substitution of 'i' for 'e')
sittin → sitting (insertion of 'g')

if this issue gets assigned, could you also please label this under hacktoberfest.
Thank You!

[srijani006]

hey @xthxr,
I noticed there’s an open PR for this issue implementing the bottom-up dynamic programming approach.
I’ve been working on an alternative solution using a top-down recursive + memoization approach, which also efficiently solves the Edit Distance problem.
Would it be okay if I open a PR showcasing this approach? It includes test cases and detailed documentation.

Thanks!