题解 | #编辑距离(一)# 内存优化版本
编辑距离(一)
http://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da
动态规划,可优化内存至 O( min( n1, n2)) 。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ int editDistance(string str1, string str2) { // write code here int n1 = str1.size(); int n2 = str2.size(); vector<int> dp(n2 + 1, 0); // 优化内存 for(int i = 1; i <= n2; ++ i) dp[i] = i; for(int i = 1; i <= n1; ++ i) { int pre = dp[0]; dp[0] = i; int temp; for(int j = 1; j <= n2; ++ j) { temp = dp[j]; if(str1[i - 1] == str2[j - 1]) { dp[j] = pre; } else { dp[j] = min(dp[j], min(pre, dp[j - 1])) + 1; } pre = temp; } } return dp[n2]; } };