题目描述

最短编辑距离的拓展  
    - 给定一个字符串 和限定修改次数 
    - 能在该修改次数内，该字符串变成目的字符串
    - 求可以变成目的字符串的个数

如果对最短编辑距离不太熟悉，可以先看看这个 最短编辑距离

样例

3 2
abc
acd
bcd
ab 1
acbd 2
输出样例：
1
3

算法1

(暴力枚举) $O(n^2)$

• 状态表示 dp[i][j]
  • 集合 ： 所有吧a中的前i个字母 变成 b中前j个字母的集合的操作集合
  • 属性 ： 所有操作中操作次数最少的方案的操作数
• 状态计算
  状态划分 以对a中的第i个字母操作不同划分
  • 在该字母之后添加
    • 添加一个字母之后变得相同，说明没有添加前a的前i个已经和b的前j-1个已经相同
    • 即 ： dp[i][j] = dp[i][j-1] + 1
  • 删除该字母
    • 删除该字母之后变得相同，说明没有删除前a中前i-1已经和b的前j个已经相同
    • 即 ： dp[i][j] = dp[i-1][j] + 1
  • 替换该字母
    • 替换说明对应结尾字母不同，则看倒数第二个
    • 即： dp[i][j] = dp[i-1][j-1] + 1
  • 啥也不做
    • 对应结尾字母相同，直接比较倒数第二个
    • 即： dp[i][j] = dp[i-1][j-1]

trikcy
- 二维字符数组的输入

C++ 代码

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 15, M = 1010;

int n, m;
int dp[N][N];
char str[M][N]; 

int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);

    for(int i = 0; i <= la; i++) dp[i][0] = i;
    for(int i = 0; i <= lb; i++) dp[0][i] = i;

    for(int i = 1; i <= la; i++)
        for(int j = 1; j <= lb; j++)
        {
            dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1;
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i] != b[j]));
        }

    return dp[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++ ) scanf("%s", str[i] + 1);  // +1 别忘了 

    while(m--)
    { 
        char s[N];
        int limit; 
        scanf("%s%d", s + 1, &limit);  // 注意这里是 s + 1

        int res = 0;
        for(int i = 0; i < n; i++)
        {
            if(edit_distance(s, str[i]) <= limit) 
                res++;
        }


        printf("%d\n", res);    
    }

    return 0;
}

错误记录

Segmentation Fault
原因（1） : vector<srting> 输入不太熟悉
改为 cin 后TLE

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;
//const int N = 10;
//int dp[N+1][N+1];

int leastEdit(string a1, string a2){
    int m = a1.size();
    int n = a2.size();
    vector<vector<int>> dp (m+1, vector<int>(n+1));

    for(int i = 0; i <= m; i++) dp[i][0] = i;
    for(int i = 0; i <= n; i++) dp[0][i] = i;

    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1;
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a1[i-1] != a2[j-1]));
        }
    }

    return dp[m][n];
}

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

    vector<string> S(n);
    for(int i = 0; i < n; i++ )  scanf("%s",S[i]);   // 改为 Cin >> S[i]  提交  超时

    while(m--)
    {
        string s_1;
        int c;
        int res = 0;
        cin >> s_1 >> c;

        for(auto s : S )
        {
            if(leastEdit(s_1,s) <= c) 
                res++;
        }

        cout << res << endl;

    }

    return 0;
}

结果出错

• 原因 ： 二维字符数组str[][] 的输入出了问题 忘了加1

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 15, M = 1010;

int n, m;
int dp[N][N];
char str[M][N]; 

int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);

    for(int i = 0; i <= la; i++) dp[i][0] = i;
    for(int i = 0; i <= lb; i++) dp[0][i] = i;

    for(int i = 1; i <= la; i++)
        for(int j = 1; j <= lb; j++)
        {
            dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1;
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i] != b[j]));
        }

    return dp[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++ ) scanf("%s", str[i]);   // 这里的问题

    while(m--)
    { 
        char s[N];
        int limit; 
        scanf("%s%d", s + 1, &limit);  // 注意这里是 s + 1

        int res = 0;
        for(int i = 0; i < n; i++)
        {
            if(edit_distance(s, str[i]) <= limit) 
                res++;
        }


        printf("%d\n", res);    
    }

    return 0;
}