编辑距离问题及其优化

For Q-583: leetcode delete-operation-for-two-strings

# Q-583: 2-D dp status
def min_distance(word1, word2)
  dp = (1 + word1.size).times.map { [0] * (1 + word2.size) }
  word2.size.times { |j| dp[0][j + 1] = j + 1 }
  word1.chars.each_with_index do |cs, i|
    dp[i + 1][0] = i + 1
    word2.chars.each_with_index do |ct, j|
      if cs == ct
        dp[i + 1][j + 1] = dp[i][j]
      else
        dp[i + 1][j + 1] = [dp[i + 1][j], dp[i][j + 1]].min + 1
      end
    end
  end
  dp.last.last
end

# Q-583: 1-D dp status
def min_distance(word1, word2)
  dp = (0..word2.size).to_a
  word1.chars.each_with_index do |cs, i|
    upleft, dp[0] = dp[0], i + 1 #important
    word2.chars.each_with_index do |ct, j|
      up = dp[j + 1]
      dp[j + 1] = cs == ct ? upleft : [up, dp[j]].min + 1 # dp[j] means left element in same layer
      upleft = up
    end
  end
  dp.last
end

p min_distance(word1 = "sea", word2 = "eat") == 2

For Q-72: edit distance

  1. upleft 初始值设置为上行首值；
  2. 在循环过程中，需要先保存上一轮的当前值，上一轮产出的upleft本轮结束前无法更新。因此，两个变量是必须的。
  3. 应当保留up, upleft, left三个值。但只有upleft需要通过上一轮次的更新来设定。这是唯一的难点。
# @param {String} word1
# @param {String} word2
# @return {Integer}
def min_distance(word1, word2)
    dp = (0..word2.size).to_a
    word1.chars.each_with_index do |cs, i|
        upleft = dp[0]
        dp[0]=i+1
        word2.chars.each_with_index do |ct, j|
            up=dp[j+1]
            if cs==ct
                dp[j+1]=upleft
            else
                dp[j+1]=[upleft, dp[j], dp[j+1]].min + 1
            end
            upleft=up
        end
    end
    dp.last
end