题目描述

编辑距离：给定 n个长度不超过10的字符串以及 m次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的 n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、 删除或替换算作一次操作。

样例

3 2
abc
acd
bcd
ab 1
acbd 2

Output:
1
3

算法1

动态规划

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1010; // 假设字符串最大长度不超过 1000

int dp[N][N]; //表示将字符串 A 的前 i 个字符变为字符串 B 的前 j 个字符所需的最小操作次数。

int main() {
    int n, m;
    cin >> n >> m;

    // 读取 n 个字符串
    vector<string> str(n);
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }

    // 处理 m 次询问
    while (m--) {
        string s;
        int cnt;
        cin >> s >> cnt; // 目标字符串和操作次数限制

        int res = 0; // 记录满足条件的字符串个数

        // 遍历每个字符串
        for (int x = 0; x < n; x++) {
            int len1 = str[x].size(), len2 = s.size();

            // 剪枝：如果两个字符串的长度差大于 cnt，不可能通过 cnt 次操作将一个字符串变为另一个字符串。
            if (abs(len1 - len2) > cnt) {
                continue;
            }

            // 初始化动态规划表
            for (int i = 0; i <= len1; i++) {
                dp[i][0] = i; // 从 str[x] 的前 i 个字符变成空串需要 i 次删除
            }
            for (int j = 0; j <= len2; j++) {
                dp[0][j] = j; // 从空串变成 s 的前 j 个字符需要 j 次插入
            }

            // 动态规划计算编辑距离
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (str[x][i - 1] == s[j - 1]) { // 当前字符相等
                        dp[i][j] = dp[i - 1][j - 1];
                    } else { // 插入、删除、替换
                        dp[i][j] = min({dp[i - 1][j - 1] + 1, // 替换
                                        dp[i - 1][j] + 1,     // 删除
                                        dp[i][j - 1] + 1});   // 插入
                    }
                }
            }

            // 如果编辑距离小于等于操作次数限制说明可以在限制内完成转换，结果 res 增加 1
            if (dp[len1][len2] <= cnt) {
                res++;
            }
        }

        // 输出满足条件的字符串个数
        cout << res << endl;
    }

    return 0;
}