Edit Distance Problem

Algorithm Steps

Let word1 and word2 be the input strings, with lengths m and n respectively.
Create a 2D table dp of dimensions (m+1) x (n+1), where dp[i][j] represents the edit distance between the first i characters of word1 and the first j characters of word2.
Initialize the first column: for each i from 0 to m, set dp[i][0] = i (representing i deletions).
Initialize the first row: for each j from 0 to n, set dp[0][j] = j (representing j insertions).
For each i from 1 to m and for each j from 1 to n:

If word1[i-1] equals word2[j-1], then set dp[i][j] = dp[i-1][j-1].
Otherwise, set dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

The edit distance is dp[m][n].

Edit Distance Program - Dynamic Programming Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    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]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

if __name__ == '__main__':
    print("Edit Distance between 'kitten' and 'sitting':", edit_distance("kitten", "sitting"))
    print("Edit Distance between 'horse' and 'ros':", edit_distance("horse", "ros"))

Edit Distance Problem

Visualization

Algorithm Steps

Edit Distance Program - Dynamic Programming Code