0

More than 1 year has passed since last update.

# Swift で Edit Distance (編集距離)

Last updated at Posted at 2021-09-12

Edit Distance を Swift で書いたのでメモ

## 解法

ロジックの詳しい解説はけんちょん本の下記項目を参照

## コード

func minDistance(_ word1: String, _ word2: String) -> Int {
let w1 = word1.map({ String(\$0) })
let w2 = word2.map({ String(\$0) })
var dp = [[Int]](repeating: [Int](repeating: Int.max, count: w2.count+1), count: w1.count+1)
dp[0][0] = 0

for i in 0..<w1.count+1 {
for j in 0..<w2.count+1 {
if i-1 >= 0 && j-1 >= 0 {
// noop
if w1[i-1] == w2[j-1] {
dp[i][j] = min(dp[i][j], dp[i-1][j-1])
}
// replace
else {
dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1)
}
}

// delete
if i-1 >= 0 {
dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
}

// insert
if j-1 >= 0 {
dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
}
}
}

return dp[w1.count][w2.count]
}

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
0