Edit distance between strings problem in Ruby (Dynamic Programming)

edit_distance_dp_in_ruby.md

Problem Introduction

The edit distance between two strings is the minimum number of operations (insertions, deletions, and substitutions of symbols) to transform one string into another. It is a measure of similarity of two strings. Edit distance has applications, for example, in computational biology, natural language processing, and spell checking. Your goal in this problem is to compute the edit distance between two strings.

Problem Description

Task.

The goal of this problem is to implement the algorithm for computing the edit distance between two strings.

Input Format.

Each of the two lines of the input contains a string consisting of lower case latin letters.

Constraints.

The length of both strings is at least 1 and at most 100.

Output Format.

Output the edit distance between the given two strings.

str1 = gets.chomp
str2 = gets.chomp
str2_len = str2.length

distance = (0..str2_len).to_a
x = nil

str1.each_char.with_index do |char1, ind1|
  char1_val = ind1 + 1

  str2.each_char.with_index do |char2,ind2|
    cost = (char1 == char2) ? 0 : 1
    x = [
      distance[ind2+1] + 1, # insertion (вставка)
      char1_val + 1,        # deletion (удаление)
      distance[ind2] + cost # substitution (замена)
    ].min

    distance[ind2] = char1_val
    char1_val = x
  end

  distance[str2_len] = x
end

puts x