Levenshtein Distance

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

Code

Algorithms

m, n = a.length, b.length
dp = Array.new(m + 1) { Array.new(n + 1, 0) }
(0..m).each { |i| dp[i][0] = i }
(0..n).each { |j| dp[0][j] = j }
(1..m).each do |i|
  (1..n).each do |j|
    dp[i][j] = a[i-1] == b[j-1] ? dp[i-1][j-1] : 1 + [dp[i-1][j], dp[i][j-1], dp[i-1][j-1]].min
  end
end
return dp[m][n]

Parameters

a(string)

First string

b(string)

Second string

Server

More Ruby 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.