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思路:普通的DP很好写,问题是路径压缩的DP压缩如果进行,空间如何重复利用,和背包问题有点像,留待第二遍再解决
class Solution {public: int minDistance(string word1, string word2) { // Start typing your C/C++ solution below // DO NOT write int main() function int ** dp = new int*[word1.size() + 1]; for(int i = 0; i < word1.size() + 1; i++){ dp[i] = new int[word2.size() + 1]; } for(int i = 0; i < word1.size() + 1; i++){ dp[i][0] = i; } for(int j = 0; j < word2.size() + 1; j++){ dp[0][j] = j; } for(int i = 1; i < word1.size() + 1; i++){ for(int j = 1; j < word2.size() + 1; j++){ if (word1[i-1] == word2[j-1]){ //相等的情况下,最后一个元素不占用操作 dp[i][j] = dp[i-1][j-1]; }else{ //delete一种串 dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1); //i和j的位置进行replace dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1); } } } int ans = dp[word1.size()][word2.size()]; for(int i = 0; i < word1.size() + 1; i++){ delete []dp[i]; } delete []dp; return ans; }};