class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ int editDistance(string str1, string str2) { // write code here int m=str1.size(); int n=str2.size(); vector<int>dp(n+1); //初始化 for(int i=0; i<=n; i++) dp[i]=i; //循环处理 for(int i=1; i<=m; i++) { int prev=dp[0];//记录左上位置 dp[0]=i; for(int j=1; j<=n; j++) { int tmp=dp[j]; if(str1[i-1]==str2[j-1]) dp[j]=prev; else dp[j]=min(prev,min(dp[j],dp[j-1]))+1; prev=tmp; } } return dp[n]; } };