首页 > 代码库 > 72. Edit Distance
72. Edit Distance
Problem statement:
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
Solution:
This is also a DP problem, which is a little complicated than 583. Delete Operation for Two Strings. We can do two more operations: insert and replace.
The dp formular is complicated when word1[i] != word2[j].
But the initialization and return value is the same.
class Solution {public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // initialize for(int i = 0; i <= m; i++){ dp[i][0] = i; } for(int j = 0; j <= n; j++){ dp[0][j] = j; } // dynamic programming for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ // two character is equal 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], min(dp[i - 1][j], dp[i][j - 1])) + 1; } } } return dp[m][n]; }};
72. Edit Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。