新实木地板的油漆有味道吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

新实木地板的油漆有味道吗？

新实木地板的油漆有味道吗？# Living

g*y2009-11-14 08:11

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面试了

t*l2009-11-14 08:11

2 楼

时间：2012/9/21
地点：广州
人物：弟弟
人数：1
签证类型：B2
签证状态：1000
签经结果：被拒
想让弟弟趁年假的时候陪父母过来，玩半个月了他再回去上班。父母在10号在沈阳签过了，结果弟弟昨天被拒了。
问：去美国做什么？
答：旅游
问：一个人去么？
答：和父母一起去
问：怎么没和父母一起签
答：父母在沈阳已经签过了
签证官：对不起，我不能给你签证。
撕条，无牢固约束力证明。。。

az2009-11-14 08:11

3 楼

有污染吗？新的需要敞一段时间呢？谢谢

h*k2009-11-14 08:11

4 楼

应该是给任意的两个单词，求他们之间的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面试了

t*l2009-11-14 08:11

5 楼

我和弟弟后来讨论了一下，可能是签证官纠结于没和父母一起签。
我家住在东北，所以爸妈在沈阳签证了。我弟弟在深圳上班，所以约的广州。当初觉得
还挺好过的，就没有认真准备。希望大家能够引以为鉴。
我觉得以后有类似情况干脆不要提跟父母一起来玩，就说一个人趁年假到美国旅游，打
算玩半个月，估计还好过一些。
弟弟不打算再签了，到时候只能让爸妈自己过来了。

过了，结果弟弟昨天被拒了。

【在 t***l 的大作中提到】

: 时间：2012/9/21
: 地点：广州
: 人物：弟弟
: 人数：1
: 签证类型：B2
: 签证状态：1000
: 签经结果：被拒
: 想让弟弟趁年假的时候陪父母过来，玩半个月了他再回去上班。父母在10号在沈阳签过了，结果弟弟昨天被拒了。
: 问：去美国做什么？
: 答：旅游

az2009-11-14 08:11

6 楼

顶一下

【在 az 的大作中提到】

: 有污染吗？新的需要敞一段时间呢？谢谢

g*y2009-11-14 08:11

7 楼

是任意给一个单词(可能错误拼写)，求它到整个字典的Min edit distance

【在 h**k 的大作中提到】

: 应该是给任意的两个单词，求他们之间的edit distance吧？
: 最简单的办法是DP，这个不需要对字典作处理。
: 更快的办法是对每个string进行预处理，好像是可以建一个prefix tree

r*o2009-11-14 08:11

8 楼

是不是说abc操作的话，distance为1?

【在 g*******y 的大作中提到】

g*y2009-11-14 08:11

9 楼

是的，a,b,c任意一种操作都是定义为distance 为1

【在 r****o 的大作中提到】

: 是不是说abc操作的话，distance为1?

r*g2009-11-14 08:11

10 楼

我们作业做过一个，就是hash table先试distance 1，再试distance 2。。。

【在 g*******y 的大作中提到】

: 是的，a,b,c任意一种操作都是定义为distance 为1

a*n2009-11-14 08:11

11 楼

http://acm.pku.edu.cn/JudgeOnline/problem?id=1035

c*p2009-11-14 08:11

12 楼

花了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