动态规划一日一题-10.4-编辑距离

编辑距离

---

给定 n个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 n和 m。

接下来 n行，每行包含一个字符串，表示给定的字符串。

再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 10。

输出格式

输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

1≤n,m≤1000

输入样例：

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
3

---

总体考察dp的方式就是同最小编辑距离是一致的，这里再次将最小编辑距离再次巩固一次。

设置一个函数，用于返回从字符串a变化到字符串b的时候，所需要的最小的次数。

主函数则用每次返回的次数与limit进行比较，如果比limit小，num++即可。

对于edit_distance函数来说：

状态表示：f [i] [j] 就是字符串a的1-i位置变化到字符串b的1-j位置所需要的最小次数

状态属性：min

base case : 一般考虑是包括f[0]的初始化

状态转移：每一次将f[i-1] [j] and f[i] [j-1] 的最小值先赋值给f[i] [j] (也就是所谓的删除和插入)

​ 一般对于字符串类型的题目来说，分界限很多是字符是否是相等的，如果相等的话，直接pass掉。

​ 如果不相等，就是各自回到原来的一步，然后做一个替换即可。

代码如下：

#include

using namespace std ;

const int N = 1010 ; 

int f[N][N] ;

char str[N][N] ;

int edit_distance(char a[] , char b[])
{
    int la = strlen(a+1) ;  int lb = strlen(b+1) ;
    
    for(int i = 1 ; i <= la ; ++i)
    {
        f[i][0] = i ;
    }
    
    for(int i = 1 ; i <= lb ;++i)
    {
        f[0][i] = i  ;
    }
    
    for(int i = 1 ; i <= la ;++i)
    {
        for(int j = 1 ; j <= lb ;++j)
        {
            f[i][j] = min(f[i-1][j] , f[i][j-1])  + 1 ;
            if(a[i] == b[j])
            {
                f[i][j] = min(f[i][j] , f[i-1][j-1]) ; 
             }
            else
            {
                f[i][j] = min(f[i][j] , f[i-1][j-1]  +1) ;
            }
        }
    }
    return f[la][lb] ;
}

int main()
{
    int n , m  ; 
    
    cin >> n >> m ;
    
    for(int i = 1 ; i <= n ;++ i)
    {
        cin >> (str[i]  +1 ); 
    }
    
    while(m--)
    {
        int num = 0 ; 
        char c[N] ;
        int limit = 0 ; 
        cin >> (c+1) >> limit ; 
        for(int i = 1 ; i <= n ;++i)
        {
            if(edit_distance(str[i] , c) <= limit)
            {
                num ++ ;
            }
        }
        cout << num << endl ; 
    }
    return  0 ; 
}