Levenshtein Distance

Calculate the Levenshtein edit distance between two strings using dynamic programming.

Code

Algorithms

m, n = len(a), len(b)
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):
        dp[i][j] = dp[i-1][j-1] if a[i-1] == b[j-1] else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]

Parameters

a(string)

First string

b(string)

Second string

Server

More Python Snippets

Capitalize First Letter

Capitalize the first letter of a string while keeping the rest unchanged.

Center String

Center a string within a given width by padding with spaces.

Check if Palindrome

Check if a string is a palindrome by comparing characters from both ends.

Compare Strings (Case Insensitive)

Compare two strings ignoring case differences.

Convert to camelCase

Convert a string to camelCase format with lowercase first letter.

Convert to kebab-case

Convert a string to kebab-case.