c********r
发帖数: 286 | 1 Find the minimum edit distance between two strings |
b***m
发帖数: 5987 | 2 标准递归题。
【在 c********r 的大作中提到】
: Find the minimum edit distance between two strings
|
b***m
发帖数: 5987 | 3 随便写了一下，请大家指正：
int EditDistance(char *s1, char *s2)
{
if( !s1 || !*s1 ) return strlen(s2);
if( !s2 || !*s2 ) return strlen(s1);
return min3(
EditDistance(s1 + 1, s2) + 1,
EditDistance(s1, s2 + 1) + 1,
EditDistance(s1 + 1, s2 + 1) + (*s1 == *s2 ? 0 : 1)
);
} |
l*********8
发帖数: 4642 | 4 这是指数级时间复杂度吧。用dp好些
【在 b***m 的大作中提到】
: 随便写了一下，请大家指正：
: int EditDistance(char *s1, char *s2)
: {
: if( !s1 || !*s1 ) return strlen(s2);
: if( !s2 || !*s2 ) return strlen(s1);
:
: return min3(
: EditDistance(s1 + 1, s2) + 1,
: EditDistance(s1, s2 + 1) + 1,
: EditDistance(s1 + 1, s2 + 1) + (*s1 == *s2 ? 0 : 1)
|
c********r
发帖数: 286 | 5 好猫兄，可否简单讲一下思路
【在 b***m 的大作中提到】
: 随便写了一下，请大家指正：
: int EditDistance(char *s1, char *s2)
: {
: if( !s1 || !*s1 ) return strlen(s2);
: if( !s2 || !*s2 ) return strlen(s1);
:
: return min3(
: EditDistance(s1 + 1, s2) + 1,
: EditDistance(s1, s2 + 1) + 1,
: EditDistance(s1 + 1, s2 + 1) + (*s1 == *s2 ? 0 : 1)
|
c********r
发帖数: 286 | 6 简单说说思路
【在 l*********8 的大作中提到】
: 这是指数级时间复杂度吧。用dp好些
|
b***m
发帖数: 5987 | 7 俺不会DP，正打算向二爷讨教。
【在 l*********8 的大作中提到】
: 这是指数级时间复杂度吧。用dp好些
|
j*****s
发帖数: 189 | 8 用DP好一些
for(int i = 1 ; i< n1 + 1; ++i){
for (int j = 1; j < n2 + 1; ++j){
if (word1[i - 1] == word2[j - 1])
{
dist[i][j] = dist[i - 1][j - 1];
}
else{
dist[i][j] = min(dist[i - 1][j - 1], dist[i - 1][j],
dist[i][j - 1]) + 1;
}
}
} |
p*****2
发帖数: 21240 | |
c********r
发帖数: 286 | 10 竟然有人把这题写成论文一般长, 正所谓经典
【在 p*****2 的大作中提到】
: 经典dp了。
|
