dictonary: distance code

给你一个字典array of strings (you may preprocess it if necessary)

任意一个单词，求最小的edit distance

一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)

快速的code出来～ 你就可以拿facebook面试了



int findMinEditDistance(const char* pszStr1, const char* pszStr2)
{
size_t N = strlen(pszStr1);
size_t M = strlen(pszStr2);

int** map = new int*[N];
for(int i=0;i {
map[i] = new int[M];
}

// map[0][0]
map[0][0] = pszStr1[0] == pszStr2[0] ? 0 : 1;

// map[1...N-1][0]
for(int i=1;i {
map[i][0] = pszStr1[i] == pszStr2[0] ? i : map[i - 1][0]+1;
}

// map[0][1...M-1]
for(int i=1; i {
map[0][i] = pszStr1[0] == pszStr2[i] ? i : map[0][i-1] + 1;
}

for(int i=1;i {
for(int j=1;j {
if (pszStr1[i] == pszStr2[j])
{
map[i][j] = map[i-1][j-1];
}
else
{
// find the min neighbor and add 1
int min = map[i-1][j-1] > map[i-1][j] ? map[i-1][j] : map[i-
1][j-1];
min = min > map[i][j-1] ? map[i][j-1] : min;
map[i][j]=min + 1;
}
}
}

//晕，忘了delete[]...

int result = map[N-1][M-1];

for(int i=0;i{
delete[] map[i];
}

delete[] map;

return result;
}


int main()
{

printf("%d\n", findMinEditDistance("abc","abcd"));
printf("%d\n", findMinEditDistance("bbc","abcd"));
printf("%d\n", findMinEditDistance("mit","bbsmit"));
printf("%d\n", findMinEditDistance("sex","fuck"));
printf("%d\n", findMinEditDistance("sina.com","sbina.ckom"));

return 0;
}