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 的大作中提到】
: 给你一个字典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 的大作中提到】
: 应该是给任意的两个单词，求他们之间的edit distance吧？
: 最简单的办法是DP，这个不需要对字典作处理。
: 更快的办法是对每个string进行预处理，好像是可以建一个prefix tree
|
r****o
发帖数: 1950 | 4 是不是说abc操作的话，distance为1?
【在 g*******y 的大作中提到】
: 给你一个字典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 的大作中提到】
: 是不是说abc操作的话，distance为1?
|
r********g
发帖数: 1351 | 6 我们作业做过一个，就是hash table先试distance 1， 再试distance 2。。。
【在 g*******y 的大作中提到】
: 是的，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 的大作中提到】
: 给你一个字典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 的大作中提到】
: 这不就是spell checker么
: 最完美的方案就是现对ngram建index,
: 然后given any word对ngram index算Levenshtein distance
: 当然不可能短时件code出来，能提到也不错
|
