【42. 编辑距离】

• 思路与最短编辑距离一样，可以参考上一篇文章
  
  最短编辑距离
  
  
  
  
  

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 15, M = 1010;
int n, m;
int f[N][N];   //动态规划数组
char str[M][N];   //所有的字符串，最多有1000个字符串，每个字符串最大长度为n

int editDistance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);
    int lc = strlen(a);
    cout<< "lc =" << lc << endl;
   
    
    for (int i = 0; i <= lb; i ++) f[0][i] = i;
    for (int i = 0; i <= la; i ++) f[i][0] = i;
    for (int i = 1; i <= la; i ++)
        for (int j = 1; j <= lb; j ++)
            {
                f[i][j] = min(f[i - 1][j] + 1, 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()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> (str[i] + 1);   //与最短编辑距离不一样，最短编辑距离只需要输入一个字符串
                                                        //而这道题是要输入n个字符串
    
    while (m --)
    {
        char s[N];
        int limit;
        cin >> s  + 1 >> limit;
        
        int res = 0;
        for (int i = 0; i < n; i ++)
        {
            if (editDistance(str[i], s) <= limit)   //枚举每一个字符串与题目规定的字符串进行比较
                res ++;
        }
        cout << res << endl;
    }
    return 0;
}

注意：区分下标从1还是从0

#include <iostream>
#include <algorithm>
#include <string.h>
//#include <cstring>
#include <string>
using namespace std;
const int N = 15;
string s;
string s1;
char s2[N];
char s3[N];

int main()
{

   cin >> s;
   cin >> s1 + 1;        //字符串不能进行+1从下标为1的地方开始

   cin >> (s2 + 1);     //输入abc
   cin >> s3;           //输入abc

    cout << strlen(s) << endl;   //字符串只有s.size()没有strlen
    cout << s.size() << endl; 
    
    cout << s2 + 1 << endl;          //正确 输出结果为abc
    cout << strlen(s2 + 1) << endl; 

    cout << s2  << endl;            //错误   输出结果为0
    cout << strlen(s2 ) << endl; 

    cout << s3 << endl;
    cout << strlen(s3 ) << endl; 

    return 0;
    //总结：字符串不能进行+1从下标为1的地方开始，想下标从1开始则需要char[],而且打印时，需要打印char[] + 1,如果只是打印char[]是空
}