股版热闹啊，我剪草剪到一半都忍不住要过来看看# Stock
g*j
1 楼
给一个dictionary，一个target string，找出edit distance 小于等于1 的所有单词
followup question：如何设计让它更加efficient
然后查了一下帖子，好几个都电话面试的这道题目！
followup question：如何设计让它更加efficient
然后查了一下帖子，好几个都电话面试的这道题目！
X*r
2 楼
真不错的说
a*0
3 楼
这个不是很简单吗 一个for loop就搞定了 每个dictionary的词试一试就可以了
我估计没理解你说的意思
【在 g***j 的大作中提到】
: 给一个dictionary，一个target string，找出edit distance 小于等于1 的所有单词
: followup question：如何设计让它更加efficient
: 然后查了一下帖子，好几个都电话面试的这道题目！
我估计没理解你说的意思
【在 g***j 的大作中提到】
: 给一个dictionary，一个target string，找出edit distance 小于等于1 的所有单词
: followup question：如何设计让它更加efficient
: 然后查了一下帖子，好几个都电话面试的这道题目！
S*g
4 楼
剪草。。。
听起来蛮香艳的。。。
【在 X*********r 的大作中提到】
: 真不错的说
听起来蛮香艳的。。。
【在 X*********r 的大作中提到】
: 真不错的说
l*a
5 楼
你这做法,每来一个单词你都要扫描一遍
简单说这种题都是先作预处理，然后对于任意输入因该可以很直接得出结果
【在 a**********0 的大作中提到】
: 这个不是很简单吗 一个for loop就搞定了 每个dictionary的词试一试就可以了
: 我估计没理解你说的意思
简单说这种题都是先作预处理，然后对于任意输入因该可以很直接得出结果
【在 a**********0 的大作中提到】
: 这个不是很简单吗 一个for loop就搞定了 每个dictionary的词试一试就可以了
: 我估计没理解你说的意思
x*x
6 楼
玛德，真毛。说刮毛就刮毛，还这么转弯抹角的
【在 S*********g 的大作中提到】
: 剪草。。。
: 听起来蛮香艳的。。。
【在 S*********g 的大作中提到】
: 剪草。。。
: 听起来蛮香艳的。。。
l*a
7 楼
大牛你前些天不说搞定offer了吗？
咋还在这埋头苦练
【在 g***j 的大作中提到】
: 给一个dictionary，一个target string，找出edit distance 小于等于1 的所有单词
: followup question：如何设计让它更加efficient
: 然后查了一下帖子，好几个都电话面试的这道题目！
咋还在这埋头苦练
【在 g***j 的大作中提到】
: 给一个dictionary，一个target string，找出edit distance 小于等于1 的所有单词
: followup question：如何设计让它更加efficient
: 然后查了一下帖子，好几个都电话面试的这道题目！
f*e
8 楼
跟这几天股市差不多，酝酿已久的庄家一出货，我们众蛙就炸锅了。所谓股市即股版，
股版即股市啊。。
学习了又
股版即股市啊。。
学习了又
a*0
9 楼
那就是设计题了 你有什么思路吗 比如先算hashcode一类的东西？
【在 l*****a 的大作中提到】
: 大牛你前些天不说搞定offer了吗？
: 咋还在这埋头苦练
【在 l*****a 的大作中提到】
: 大牛你前些天不说搞定offer了吗？
: 咋还在这埋头苦练
x*x
10 楼
出啥货？出球货
【在 f*******e 的大作中提到】
: 跟这几天股市差不多，酝酿已久的庄家一出货，我们众蛙就炸锅了。所谓股市即股版，
: 股版即股市啊。。
: 学习了又
【在 f*******e 的大作中提到】
: 跟这几天股市差不多，酝酿已久的庄家一出货，我们众蛙就炸锅了。所谓股市即股版，
: 股版即股市啊。。
: 学习了又
l*a
11 楼
对于字典里每个单词
得到edit distance<=1所有单词（不一定在字典中）
比方说word ==>A,B,C,word
then A==>word
B==>word
C==>word
word==>word
means if input is A/B/C/word, word is one of those edit distance<=1 and also
in the dictionary
create a hashMap based on this,
one word can map to several words...
after the pre-processing then each time u can use O(1) to get the result
【在 a**********0 的大作中提到】
: 那就是设计题了 你有什么思路吗 比如先算hashcode一类的东西？
得到edit distance<=1所有单词（不一定在字典中）
比方说word ==>A,B,C,word
then A==>word
B==>word
C==>word
word==>word
means if input is A/B/C/word, word is one of those edit distance<=1 and also
in the dictionary
create a hashMap based on this,
one word can map to several words...
after the pre-processing then each time u can use O(1) to get the result
【在 a**********0 的大作中提到】
: 那就是设计题了 你有什么思路吗 比如先算hashcode一类的东西？
a*0
12 楼
有道理啊 那就是 constant的时间复杂度了
also
【在 l*****a 的大作中提到】
: 对于字典里每个单词
: 得到edit distance<=1所有单词（不一定在字典中）
: 比方说word ==>A,B,C,word
: then A==>word
: B==>word
: C==>word
: word==>word
: means if input is A/B/C/word, word is one of those edit distance<=1 and also
: in the dictionary
: create a hashMap based on this,
also
【在 l*****a 的大作中提到】
: 对于字典里每个单词
: 得到edit distance<=1所有单词（不一定在字典中）
: 比方说word ==>A,B,C,word
: then A==>word
: B==>word
: C==>word
: word==>word
: means if input is A/B/C/word, word is one of those edit distance<=1 and also
: in the dictionary
: create a hashMap based on this,
c*y
13 楼
这空间复杂度是不是一下就多了平均字长倍？这算是做index了吧。
【在 a**********0 的大作中提到】
: 有道理啊 那就是 constant的时间复杂度了
:
: also
【在 a**********0 的大作中提到】
: 有道理啊 那就是 constant的时间复杂度了
:
: also
A*i
14 楼
隐约觉得得用trie
l*a
15 楼
空间时间一般来说无法两全吧
【在 c*******y 的大作中提到】
: 这空间复杂度是不是一下就多了平均字长倍？这算是做index了吧。
【在 c*******y 的大作中提到】
: 这空间复杂度是不是一下就多了平均字长倍？这算是做index了吧。
p*u
16 楼
说下我的想法，用字典树trie
首先，把输入的dictionary预处理为trie
然后，有两个子问题：
1，从trie的某个节点出发，找到完全一样的字符串
2，从trie的某个节点出发，找到edit distance <= 1的字符串
从任意一个节点开始，有4种情况：
1，多了一个字符
2，少了一个字符
3，字符一样
4，字符不一样
最坏时间复杂度就是遍历了整个trie
【在 g***j 的大作中提到】
: 给一个dictionary，一个target string，找出edit distance 小于等于1 的所有单词
: followup question：如何设计让它更加efficient
: 然后查了一下帖子，好几个都电话面试的这道题目！
首先，把输入的dictionary预处理为trie
然后，有两个子问题：
1，从trie的某个节点出发，找到完全一样的字符串
2，从trie的某个节点出发，找到edit distance <= 1的字符串
从任意一个节点开始，有4种情况：
1，多了一个字符
2，少了一个字符
3，字符一样
4，字符不一样
最坏时间复杂度就是遍历了整个trie
【在 g***j 的大作中提到】
: 给一个dictionary，一个target string，找出edit distance 小于等于1 的所有单词
: followup question：如何设计让它更加efficient
: 然后查了一下帖子，好几个都电话面试的这道题目！
相关阅读
大家快去菠菜吧“Why can’t you be more like China?” (转载)俄罗斯要破产了WMT 54以下可以介入吸毒毁一生，藏金穷三代枪枪你投降么Fidelity自家有最低投资额500美刀的Mutual Fund么？今天小小人分析师一个人来吃寿司，哭了IB现在收Exposure fees，请问哪些Broker不收吗？开始爆乳吧YHOO拆分BABA失败大众加入工会了大水枪一定股市赚翻了，因为他昨天大市趋稳，VIX 走低，UVXY 要完油还有得跌。版主大牛，上一次选股比赛结束了吗？I set a prel target for next yr巴菲特给二奶留的一笔钱，遗嘱是这么写的原来NUGT也是从天上下来的【征文】TA对左脑发达的同学有用