g*******y 发帖数: 1930 | 1 给你一个字典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面试了 |
h**k 发帖数: 3368 | 2 应该是给任意的两个单词,求他们之间的edit distance吧?
最简单的办法是DP,这个不需要对字典作处理。
更快的办法是对每个string进行预处理,好像是可以建一个prefix tree
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个字典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面试了
|
g*******y 发帖数: 1930 | 3 是任意给一个单词(可能错误拼写),求它到整个字典的Min edit distance
【在 h**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是给任意的两个单词,求他们之间的edit distance吧? : 最简单的办法是DP,这个不需要对字典作处理。 : 更快的办法是对每个string进行预处理,好像是可以建一个prefix tree
|
r****o 发帖数: 1950 | 4 是不是说abc操作的话,distance为1?
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个字典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面试了
|
g*******y 发帖数: 1930 | 5 是的,a,b,c任意一种操作都是定义为distance 为1
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是说abc操作的话,distance为1?
|
r********g 发帖数: 1351 | 6 我们作业做过一个,就是hash table先试distance 1, 再试distance 2。。。
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是的,a,b,c任意一种操作都是定义为distance 为1
|
a****n 发帖数: 1887 | |
c****p 发帖数: 32 | 8 花了20分钟验证,20分钟coding+debug...这么慢行不行啊...
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]
f |
M**********e 发帖数: 211 | 9 这不就是spell checker么
最完美的方案就是现对ngram建index,
然后given any word对ngram index算Levenshtein distance
当然不可能短时件code出来,能提到也不错
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你一个字典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面试了
|
p********7 发帖数: 549 | 10 是每个词都遍历一次字典算 distance么? 建立index具体点呢?谢谢
【在 M**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这不就是spell checker么 : 最完美的方案就是现对ngram建index, : 然后given any word对ngram index算Levenshtein distance : 当然不可能短时件code出来,能提到也不错
|