题目链接: 899. 编辑距离
主体思路
就是把 902. 最短编辑距离 按照要求重复就好
注意细节
- 由于本程序的核心代码复用了902的,需要一个额外的函数来调整输入
- 由于核心代码是复用了902题的,剩下的难点反而是处理输入,一不小心就会搞成要用两个字符串数组
基础写法
package main
import "fmt"
//复用902的核心代码
func dist(N, M int, n, m string) int {
var (
min = func(i, j int) int { if i < j { return i }; return j }
dp = make([][]int, N + 1)
)
for i := range dp { dp[i] = make([]int, M + 1) }
for i := 0; i <= N; i++ { dp[i][0] = i }
for j := 0; j <= M; j++ { dp[0][j] = j }
for i := 1; i <= N; i++ {
for j := 1; j <= M; j++ {
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
if n[i] == m[j] {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
} else { dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1) }
}
}
return dp[N][M]
}
// 调整输入格式用的函数
func cal(a, b string) int {
N, M := len(a), len(b)
n := " " + a
m := " " + b
return dist(N, M, n, m)
}
func main() {
var (
n, m int
tmp string
base []string
)
fmt.Scanf("%d%d", &n, &m)
for i := 0; i < n; i++ {
fmt.Scanf("%s", &tmp)
base = append(base, tmp)
}
for m > 0 {
m -= 1
var (
search string
limit int
)
fmt.Scanf("%s%d", &search, &limit)
ans := 0
for i := 0; i < n; i++ {
if cal(base[i], search) <= limit { ans += 1 }
}
fmt.Println(ans)
}
}