题解 | #编辑距离(一)# 内存优化版本
编辑距离(一)
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];
}
};
