Rosetta Code

Levenshtein distance

Compute edit distance with insert, delete, and substitute operations using a single rolling row.

Edit the source, then Run. Checks start after your first Run. Ctrl/⌘ + Enter runs; Tab indents. Preview services use sample data and never contact a real service.

Sourcerosettacode/popular/levenshtein_distance.vibe
def index_row(length: int) -> array<int>
  row: array<int> = []
  index = 0
  while index <= length
    row = row + [index]
    index = index + 1
  end
  row
end

def smallest(a: int, b: int, c: int) -> int
  value = a
  if b < value
    value = b
  end
  if c < value
    value = c
  end
  value
end

def levenshtein(left: string, right: string) -> int
  if left.length > right.length
    swap = left
    left = right
    right = swap
  end

  previous = index_row(left.length)
  right_index = 0
  while right_index < right.length
    current = [right_index + 1]
    left_index = 0
    while left_index < left.length
      if left.chars.fetch(left_index) == right.chars.fetch(right_index)
        value = previous.fetch(left_index)
      else
        deletion = previous.fetch(left_index + 1) + 1
        insertion = current.fetch(left_index) + 1
        substitution = previous.fetch(left_index) + 1
        value = smallest(deletion, insertion, substitution)
      end
      current = current + [value]
      left_index = left_index + 1
    end
    previous = current
    right_index = right_index + 1
  end

  previous.fetch(previous.length - 1)
end

def run -> { kitten_sitting: int, reverse_invariant: bool, rosettacode_raisethysword: int }
  {
    kitten_sitting: levenshtein("kitten", "sitting"),
    rosettacode_raisethysword: levenshtein("rosettacode", "raisethysword"),
    reverse_invariant: levenshtein("kitten", "sitting") == levenshtein("kitten".reverse, "sitting".reverse)
  }
end

Output

Click Run example to see the result.

Code checks

Run once to load the checker. Your code stays in this browser.