🐸

[鉄則B20] Edit Distance

2024/03/30に公開

Ruby

知ってないと解けないDP問題。

問題の要約

何回の操作で同じ文字になるか？

シミュレーション

たとえば abc を xyb に合わせるには次の3回で、

	操作	変更後
1	a を x に変更する	xbc
2	y を追加する	xybc
3	c を削除する	xyb

逆の場合も、

	操作	変更後
1	x を a に変更する	ayb
2	y を削除する	ab
3	c を追加する	abc

3回になる。

解説の模範解答風 (AC)

854 ms

A = gets.strip  # => "abc"
B = gets.strip  # => "xyb"
H = A.size      # => 3
W = B.size      # => 3
dp = Array.new(H.next) { Array.new(W.next) }
dp[0][0] = 0
(0..H).each do |y|
  (0..W).each do |x|
    case
    when y >= 1 && x >= 1 && A[y - 1] == B[x - 1] # 同じ場合
      dp[y][x] = [
        dp[y - 1][x] + 1,                         # 削除(上+1)
        dp[y][x - 1] + 1,                         # 挿入(左+1)
        dp[y - 1][x - 1],                         # 維持(左上)
      ].min
    when y >= 1 && x >= 1                         # 同じでない場合
      dp[y][x] = [
        dp[y - 1][x] + 1,                         # 削除(上+1)
        dp[y][x - 1] + 1,                         # 挿入(左+1)
        dp[y - 1][x - 1] + 1,                     # 変更(左上+1)
      ].min
    when y >= 1
      dp[y][x] = dp[y - 1][x] + 1                 # 左端を連番にする
    when x >= 1
      dp[y][x] = dp[y][x - 1] + 1                 # 一行目を連番にする
    end
  end
end
p dp[H][W]      # => 3

	-	x	y	b
-	0	1	2	3
a	1	1	2	3
b	2	2	2	2
c	3	3	3	3

y	x	比較	操作	結果
1	1	"a" != "x"	変更(左上+1)	0 → 1
1	2	"a" != "y"	変更(左上+1) または挿入(左+1)	1 → 2
1	3	"a" != "b"	変更(左上+1) または挿入(左+1)	2 → 3
2	1	"b" != "x"	変更(左上+1) または削除(上+1)	1 → 2
2	2	"b" != "y"	変更(左上+1)	1 → 2
2	3	"b" == "b"	維持(左上)	2 → 2
3	1	"c" != "x"	変更(左上+1) または削除(上+1)	2 → 3
3	2	"c" != "y"	変更(左上+1) または削除(上+1)	2 → 3
3	3	"c" != "b"	変更(左上+1) または削除(上+1)	2 → 3

不思議なことに dp の表は、たしかに辻褄があっている。

表をみるコツとして、左・上・左上との差分を見て、差分があれば三方の最小値から来ているのがわかる。差分がない場合は左上から来ているのがわかる。

リファクタリング後 (AC)

846 ms

A = gets.strip  # => "abc"
B = gets.strip  # => "xyb"
H = A.size      # => 3
W = B.size      # => 3
dp = Array.new(H.next) { Array.new(W.next) }
dp[0][0] = 0
(1..W).each { |x| dp[0][x] = x } # 一行目を連番にする
(1..H).each { |y| dp[y][0] = y } # 左端を連番にする
(1..H).each do |y|
  (1..W).each do |x|
    delete    = dp[y - 1][x] + 1     # 削除(上+1)
    insert    = dp[y][x - 1] + 1     # 挿入(左+1)
    no_change = dp[y - 1][x - 1]     # 維持(左上)
    change    = dp[y - 1][x - 1] + 1 # 変更(左上+1)
    if A[y - 1] == B[x - 1]
      dp[y][x] = [delete, insert, no_change].min
    else
      dp[y][x] = [delete, insert, change].min
    end
  end
end
p dp[H][W]      # => 3

一行目と左端の連番を事前に書き込んでループ内の条件を減らしたもの。

まとめ

操作	コード	向き	補足
削除	dp[y - 1][x] + 1	↓
挿入	dp[y][x - 1] + 1	→
維持	dp[y - 1][x - 1]	↘️	A[y - 1] == B[x - 1]
変更	dp[y - 1][x - 1] + 1	↘️	A[y - 1] != B[x - 1]

一行目と左端は連番にしておく。