s******t
发帖数: 169 | 1 题意：
给一个字典，里面有一堆词。然后给一个词，word，求返回，与word编辑距离<=1的所
有出现在字典里的词。
比如说{cat, fat, mat, at, yes, no}, word="cat"返回{cat, fat, mat, at}
被爆了。求解法 | A*****i
发帖数: 3587 | | s******t
发帖数: 169 | 3 详细点说说？
【在 A*****i 的大作中提到】
: hashtable就可以
| s*w
发帖数: 729 | 4 两种方法
1. 笨办法：遍历字典(n个词），挨个计算与给定 word 的 edit distance。 O(n)
2. 好点的办法: 生成所有edit distannce为1 的词，查看是否在字典中
假设给定 word 有 k个字母
2a. 挨个删除字母， O(k)
2b. 挨个换字母, O(25*k) = O(k)
2c. 挨个加入字母 O(26*(k+1)) =O(k)
【在 s******t 的大作中提到】
: 题意：
: 给一个字典，里面有一堆词。然后给一个词，word，求返回，与word编辑距离<=1的所
: 有出现在字典里的词。
: 比如说{cat, fat, mat, at, yes, no}, word="cat"返回{cat, fat, mat, at}
: 被爆了。求解法
| h******d
发帖数: 6 | | s******t
发帖数: 169 | 6 办法2不错。: )
不过复杂度有问题吧，这样假设删完一个字母以后在字典中查的复杂度是O(1)了。应该
是 O(k*k)?
【在 s*w 的大作中提到】
: 两种方法
: 1. 笨办法：遍历字典(n个词），挨个计算与给定 word 的 edit distance。 O(n)
: 2. 好点的办法: 生成所有edit distannce为1 的词，查看是否在字典中
: 假设给定 word 有 k个字母
: 2a. 挨个删除字母， O(k)
: 2b. 挨个换字母, O(25*k) = O(k)
: 2c. 挨个加入字母 O(26*(k+1)) =O(k)
| j*****y
发帖数: 1071 | 7 这可以用剪枝来优化吧，
只需要找出 edit distance是 0或者 1的
distance 0: equal
distance 1: 只需要考虑 word.length(), word.length() + 1, word.length() -1
的长度的单词
【在 s******t 的大作中提到】
: 题意：
: 给一个字典，里面有一堆词。然后给一个词，word，求返回，与word编辑距离<=1的所
: 有出现在字典里的词。
: 比如说{cat, fat, mat, at, yes, no}, word="cat"返回{cat, fat, mat, at}
: 被爆了。求解法
| c*****a
发帖数: 808 | 8 跟leetcode/cc150的某题差不多啊
public static List findDistanceOne(Set dict, String str){
List res = new ArrayList();
for(String s: bfs(str))
if(dict.contains(s)) res.add(s);
return res;
}
public static Set bfs(String s){
Set set = new TreeSet();
set.add(s);
for(int i =0;i
set.add(s.substring(0,i)+s.substring(i+1));
for(int i =0;i
for(char j='a';j<='z';j++)
set.add(s.substring(0,i)+j+s.substring(i));
for(int i=0;i
for(char j='a';j<='z';j++){
char[] ch = s.toCharArray();
if(ch[i]!=j){
ch[i]=j;
String nstr = new String(ch);
set.add(nstr);
}
}
}
return set;
} | M********5
发帖数: 715 | 9 如果我还记得的话，careercup这题有个前提吧，好象是说所有的word长度都是一样的？
str){
【在 c*****a 的大作中提到】
: 跟leetcode/cc150的某题差不多啊
: public static List findDistanceOne(Set dict, String str){
: List res = new ArrayList();
: for(String s: bfs(str))
: if(dict.contains(s)) res.add(s);
: return res;
: }
: public static Set bfs(String s){
: Set set = new TreeSet();
: set.add(s);
| s******t
发帖数: 169 | 10 还记得链接不？求一个
str){
【在 c*****a 的大作中提到】
: 跟leetcode/cc150的某题差不多啊
: public static List findDistanceOne(Set dict, String str){
: List res = new ArrayList();
: for(String s: bfs(str))
: if(dict.contains(s)) res.add(s);
: return res;
: }
: public static Set bfs(String s){
: Set set = new TreeSet();
: set.add(s);
| | | c*****a
发帖数: 808 | 11 加上length-1的那些substring就行了吧
的？
【在 M********5 的大作中提到】
: 如果我还记得的话，careercup这题有个前提吧，好象是说所有的word长度都是一样的？
:
: str){
| y****n
发帖数: 743 | 12 遍历字典中的词
计算长度差：
-1：原词减字对比
0 ：两词减字对比
1 ：字典词减字对比
最坏情况：O(n*s); n=字典词书, s=词长度
【在 s******t 的大作中提到】
: 题意：
: 给一个字典，里面有一堆词。然后给一个词，word，求返回，与word编辑距离<=1的所
: 有出现在字典里的词。
: 比如说{cat, fat, mat, at, yes, no}, word="cat"返回{cat, fat, mat, at}
: 被爆了。求解法
| l*****a
发帖数: 14598 | 13 时间上很差
空间上不错
【在 y****n 的大作中提到】
: 遍历字典中的词
: 计算长度差：
: -1：原词减字对比
: 0 ：两词减字对比
: 1 ：字典词减字对比
: 最坏情况：O(n*s); n=字典词书, s=词长度
| l***i
发帖数: 1309 | 14 each word s in the dictionary is mapped/hashed into multiple keys, where
each key is the word minus one letter, for example, if word is "cat"
then there are 4 entries with value "cat"
key="cat"
key="ca"
key="ct"
key="at"
Now two words have distance of 1 iff they have a common key.
Proof:
1. if two words w1 and w2 have distance of 1, then it is either an insert/
delete/change. All three will have w1 and w2 map into one common key.
2. if two words w1 and w2 have a common key, then that key is either the
word itself or the word remove one letter. It is easily verified that w1 and
w2 have distance at most 1.
Now each word w is mapped into at most |w| keys, where |w| is the number of
letters in w. Since English words are in general short, less than 15 letters
. We use space O(n * max|w|) and all words with distance at most 1 will be
in the same hash table entry. The value of each hashtable entry is a list of
words, and they all have distance at most 1 between each other. | x*****0
发帖数: 452 | |
|
