首页 > 代码库 > Edit Distance
Edit Distance
Given 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
分析：用动态规划来解，f[i][j]表示word1[0,i-1]与word2[0,j-1]的edit distance。当word1[i] == word2[j]时，f[i][j] = f[i-1][j-1]；否则，f[i][j]为f[i-1][j]+1（delete a character）、f[i][j-1]+1（insert a character）、f[i-1][j-1]+1（replace a character）中的最小值。
1 class Solution { 2 public: 3 int minDistance(string word1, string word2) { 4 int m = word1.length(), n = word2.length(); 5 if(m == 0 || n == 0) return abs(m-n); 6 int record[m+1][n+1]; 7 for(int i = 0; i <= m; i++) 8 record[i][0] = i; 9 for(int j = 0; j <= n; j++)10 record[0][j] = j;11 for(int i = 1; i <= m; i++)12 for(int j = 1; j <= n; j++){13 if(word1[i-1] == word2[j-1]) record[i][j] = record[i-1][j-1];14 else{15 int min_step = min(record[i-1][j],record[i][j-1]);16 record[i][j] = min(min_step,record[i-1][j-1]) + 1;17 }18 }19 return record[m][n];20 }21 };
Edit Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。