动态规划

计算出最接近的单词

通过最小的改动，使2个单词相同。

从第一个单词wordA，到第二个单词wordB，有三种操作：
- 删除一个字符
- 添加一个字符
- 替换一个字符

综合上述三种操作，用最少步骤将单词wordA变到单词wordB，我们就称这个值为两个单词之间的距离。比如 pr1ce -> price，只需要将 1 替换为 i 即可，所以两个单词之间的距离为1。pr1ce -> prize，要将 1 替换为 i ，再将 c 替换为 z ，所以两个单词之间的距离为2

求解任意两个单词之间的距离，只要知道之前单词组合的距离即可。我们用dp[i][j]表示第一个字符串wordA[0…i] 和第2个字符串wordB[0…j] 的最短编辑距离，那么这个动态规划的两个重要参数分别是：

初始化状态为数组a[][] ={0}
状态转移方程：a[i+1][j+1] = max(a[i ][j ], a[i + 1][j], a[i][j + 1]) //最大相同数

#include <iostream>
#include <string>
#include <algorithm>
#include<vector>
using namespace std;
int wordDistance(string w1, string w2){
    int size1 = w1.size();
    int size2 = w2.size();
    vector<vector<int>> a(size1+1, vector<int>(size2+1));
    for (size_t i = 0; i < size1; i++)
    {
        for (size_t j = 0; j < size2; j++)
        {
            if (w1[i] == w2[j]){
                a[i+1][j+1] = a[i][j]+1;
            }
            else{

                a[i+1][j+1] = max(max(a[i][j + 1], a[i + 1][j]),a[i][j]) ;
            }
        }
    }
    int size = size2>size1 ? size2 : size1;
    return (size - a[size1][size2]);
}
int main()
{
    cout << wordDistance("asdfg", "gfdsaadf")<<endl;
}

下面的是两个单词的距离。上面是最大连续相同数。

int WordDistance(string wordA, string wordB){

    int sizeA = wordA.size();
    int sizeB = wordB.size();
    vector<vector<int>>a(sizeA+1,vector<int>(sizeB+1));

    for (size_t i = 0; i <= sizeA; i++)
    {
        for (size_t j = 0; j <= sizeB; j++)
        {
            if (i == 0){
                a[i][j] = j;
            }
            else if (j == 0){
                a[i][j] = i;
            }
            else if (wordA[i - 1] == wordB[j - 1]){
                a[i][j] = a[i - 1][j - 1];
            }
            else{
                a[i][j] = min(min(a[i - 1][j - 1], a[i - 1][j]), a[i][j - 1]) + 1;
            }
        }

    }
    return a[sizeA][sizeB];

}

原文链接: https://www.cnblogs.com/yuguangyuan/p/5835866.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/398221

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

相关推荐