给定两个字符串 str1 和 str2 ,请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作:
1.插入一个字符
2.删除一个字符
3.修改一个字符。
字符串长度满足 ,保证字符串中只出现小写英文字母。
"nowcoder","new"
6
"nowcoder"=>"newcoder"(将'o'替换为'e'),修改操作1次 "nowcoder"=>"new"(删除"coder"),删除操作5次
"intention","execution"
5
一种方案为: 因为2个长度都是9,后面的4个后缀的长度都为"tion",于是从"inten"到"execu"逐个修改即可
"now","nowcoder"
5
#define min(a,b) (a<b?a:b) #define min3(a,b,c) (a<min(b,c)?a:min(b,c)) int editDistance(char* str1, char* str2 ) { int dp[1001][1001], i, j; for(i=1; i<=strlen(str1); i++) dp[i][0] = i; for(i=1; i<=strlen(str2); i++) dp[0][i] = i; for(i=1; i<=strlen(str1); i++) { for(j=1; j<=strlen(str2); j++) { if(str1[i-1]==str2[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min3(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1; } } return dp[i-1][j-1]; }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ int editDistance(char* s, char* t ) { // write code here int m = strlen(s); int n = strlen(t); // if (m >= n + 2) // return false; int** mined = (int**)malloc(sizeof(int*) * (m + 1)); for (int i = 0; i <= m; i++) { mined[i] = (int*)calloc(n + 1, sizeof(int)); } for (int ii = 1; ii <= m; ii++) { mined[ii][0] = ii; } for (int iii = 1; iii <= n; iii++) { mined[0][iii] = iii; } for (int j = 1; j <= m; j++) { for (int k = 1; k <= n; k++) { if (s[j - 1] == t[k - 1]) { mined[j][k] = mined[j - 1][k - 1]; } else { if ((mined[j - 1][k - 1] + 1) < (mined[j][k - 1] + 1)) { if ((mined[j - 1][k - 1] + 1) < (mined[j - 1][k] + 1)) { mined[j][k] = (mined[j - 1][k - 1] + 1); } else { mined[j][k] = (mined[j - 1][k] + 1); } } else { if ((mined[j][k - 1] + 1) < (mined[j - 1][k] + 1)) { mined[j][k] = (mined[j ][k - 1] + 1); } else { mined[j][k] = (mined[j - 1][k] + 1); } } //mined[j][k]=((mined[j-1][k-1]+1)>(mined[j][k-1]+1):) } } } // if (mined[m][n] == 1) // return true; return mined[m][n]; }