Edit Distance

    xiaoxiao2021-03-26  10

    编辑距离


    问题描述:leetcode:72Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

    You have the following 3 operations permitted on a word:

    a) Insert a character b) Delete a character c) Replace a character

    给定两个字符串word1和word2;求把word1转化为word2需要的最少的步骤。对于字符串可以有以下操作:

    a) 插入一个字符 b) 删除一个字符 c) 替换一个字符

    思路:

    先考虑边界情况,当word1有输入,word2为空时;所需要的步骤为word1的长度。

    先考虑边界情况,当word1为空,word2有输入时;所需要的步骤为word2的长度。

    当word1和word2都有输入时,对于dp[i][j]为何值取决于word1[i-1]与word2[j-1]是否相等,当不相等时:

    dp[i][j] = dp[i-1][j] , dp[i][j-1], dp[i-1][j-1]中的最小值加1;

    如下图所示: 由于a 与 d 不相等,所以dp[1][4]的值取决于图中所示三个值,取三个值中的最小值然后加1.

    当word1[i-1]与word2[j-1]相等时: dp[i][j]=dp[i-1][j-1]

    如图所示:


    我自己的渣代码,虽然AC但是可以看到一堆补丁:

    int minDistance(string word1, string word2) { int row = word1.length(); int col = word2.length(); //如何使得可以根据row和col求得数组的大小 if(row==0&&col==0) return 0; else if(row==0) return col; else if(col==0) return row; int a = 0; int b = 0; int ans[row][col]; string::iterator rowbegin=word1.begin(); string::iterator colbegin=word2.begin(); for (string::iterator i=word2.begin(); i!=word2.end(); i++){ if (*i == *rowbegin) { ans[a][b] = b; } else if(b==0){ ans[a][b] = 1; } else{ ans[a][b] = ans[a][b-1]+1; } b++; } a = 1; b = 0; for (string::iterator j=word1.begin()+1; j!=word1.end(); j++){ if (*j == *colbegin) { ans[a][b] = a; } else{ ans[a][b] = ans[a-1][b]+1; } a++; } a = 1; b = 1; for (string::iterator i=rowbegin+1;i!=word1.end(); i++){ b = 1; for (string::iterator j=colbegin+1;j!=word2.end(); j++){ if (*i==*j) { ans[a][b] = ans[a-1][b-1]; } else{ ans[a][b] = min(min(ans[a-1][b],ans[a][b-1]),ans[a-1][b-1])+1; } b++; } a++; } return ans[row-1][col-1]; }

    leetcode优秀代码:

    int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0)); for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1)); } } return dp[m][n]; }

    语法注意点:

    string是可以使用str[i]来获取第i+1个字符的,不一定非得使用iterator:

    if (word1[i - 1] == word2[j - 1]);

    定义了一个二维数组,行列数都已知: 注意:最后两个 > >中间有个空格。

    vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));

    以上之所以要m+1和n+1是因为考虑到边界,当一个word没有输入时的情况;所以数组的大小要大一点。

    转载请注明原文地址: https://ju.6miu.com/read-600058.html

    最新回复(0)