Edit Distance（C++编辑距离）

我就是我 2022-10-11 10:56 169阅读 0赞

（1）动态规划

  1. class Solution {
  2. public:
  3.     int minDistance(string w1, string w2) {
  4.         int m=w1.length(),n=w2.length();
  5.         vector<vector<int>> v(m+1,vector<int>(n+1,0));
  7.         for(int i=0;i<m+1;i++) {
  8.             for(int j=0;j<n+1;j++) {
  9.                 if(i==0 && j==0) v[i][j]=0;
  10.                 else if(i==0 && j>0) v[i][j]=j;
  11.                 else if(i>0 && j==0) v[i][j]=i;
  12.                 else if(w1[i-1]==w2[j-1]) v[i][j]=v[i-1][j-1];
  13.                 else v[i][j]=min(v[i-1][j],min(v[i][j-1],v[i-1][j-1]))+1;
  14.             }
  15.         }
  16.         return v[m][n];
  17.     }
  18. };

发表评论

表情：
评论列表 （有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

    相关 编辑框Edit Control

    鸡啄米上一节讲了[静态文本框][Link 1]，本节要讲的编辑框（Edit Control）同样是一种很常用的控件，我们可以在编辑框中输入并编辑文本。在前面加法计算器的例子中已

    浅浅的花香味﹌浅浅的花香味﹌/ 0 赞/ 364 阅读

    相关 编辑距离

    一、问题描述 设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：   （1）删除一个字符；   （2）插入一个字符；   （3）

    逃离我推掉我的手逃离我推掉我的手/ 0 赞/ 388 阅读