l******0
发帖数: 244 | 1 如果一个词典 Dictionary 包含英文中的单词，将一个 String 分割为合法的单词。假
设 Dictionary 存在一个 HashSet 中。
String str = "Iloveyou"
分割为 "I love you".
String segment(String str, HashSet dictionary){
String segmented="";
// Iloveyou
int size = str.length()+1;
int j = 0;
int i;
for(i=1; i
String subStr = str.substring(j,i);
if(dictionary.contains(subStr)){
segmented += subStr + " ";
j = i;
}
}
if(j==i-1){
return segmented;
}else{
return null;
}
}
谁能写一个 recursive 的版本？ |
f*******n
发帖数: 12623 | |
l******0
发帖数: 244 | 3 如果输入是 "goodsdelivery", 输出就是 good-s-delivery, 上面那个就不好。这时候
最好匹配字典中长度最大的单词，得到 goods-delivery。这种情况下，那个
iterative 的 function 就比较难处理。
【在 f*******n 的大作中提到】
: iterative当然比recursive好
|
W***o
发帖数: 6519 | 4 it could also be good-sde-liver-y ?
【在 l******0 的大作中提到】
: 如果输入是 "goodsdelivery", 输出就是 good-s-delivery, 上面那个就不好。这时候
: 最好匹配字典中长度最大的单词，得到 goods-delivery。这种情况下，那个
: iterative 的 function 就比较难处理。
|
l******0
发帖数: 244 | 5 Possible, but unlikely, since 'sde' shouldn't be an entry in a 'normal'
dictionary. Here want to focus on the algorithm itself, although 'sde' could
be an entry in a domain specific dictionary.
【在 W***o 的大作中提到】
: it could also be good-sde-liver-y ?
|
l*******m
发帖数: 1096 | 6 你这个有问题...比如“nationalpark”. 应该是"national park"
但是你的只会返回null
【在 l******0 的大作中提到】
: 如果一个词典 Dictionary 包含英文中的单词，将一个 String 分割为合法的单词。假
: 设 Dictionary 存在一个 HashSet 中。
: String str = "Iloveyou"
: 分割为 "I love you".
: String segment(String str, HashSet dictionary){
: String segmented="";
:
: // Iloveyou
: int size = str.length()+1;
: int j = 0;
|
p*****2
发帖数: 21240 | |
l******0
发帖数: 244 | 8 是，取决于词典；先找到 nation, 然后剩下的 alpark 找不到一个 match, 切分不完
整，所以返回 null
所以，最好是找最大单词来匹配。一个实际可用的 segmenter，最大匹配也有问题，最
佳的需要用到概率，也就是额外的数据来支持最优选择。
这里只想练习下算法，所以上面的可行。
【在 l*******m 的大作中提到】
: 你这个有问题...比如“nationalpark”. 应该是"national park"
: 但是你的只会返回null
|
l******0
发帖数: 244 | 9 你给个 working 的 recursive 的。
【在 p*****2 的大作中提到】
: 这个算法根本就不对吧。
|
l******0
发帖数: 244 | 10 确实有问题， 简单化了
【在 l*******m 的大作中提到】
: 你这个有问题...比如“nationalpark”. 应该是"national park"
: 但是你的只会返回null
|
p*****2
发帖数: 21240 | 11
dict =
'I': true
'love': true
'you': true
dfs = (str, curr, res)->
if curr is str.length
return console.log res.join(" ")
for i in [curr...str.length]
sub = str[curr..i]
if dict[sub]
res.push sub
dfs str, i+1, res
res.pop
break_word = (str)->
dfs str, 0, []
break_word "Iloveyou"
【在 l******0 的大作中提到】
: 你给个 working 的 recursive 的。
|
b*******s
发帖数: 5216 | 12 你这个字典效率太差了，推荐你看看suffix tree
【在 l******0 的大作中提到】
: 如果一个词典 Dictionary 包含英文中的单词，将一个 String 分割为合法的单词。假
: 设 Dictionary 存在一个 HashSet 中。
: String str = "Iloveyou"
: 分割为 "I love you".
: String segment(String str, HashSet dictionary){
: String segmented="";
:
: // Iloveyou
: int size = str.length()+1;
: int j = 0;
|
g*******t
发帖数: 7704 | 13 这个问题如果深究，就复杂了， 还牵扯到拼写错误， 相识程度，
人工智能问题， |
l*******m
发帖数: 1096 | 14 牛人写的就是漂亮。这是一道经典的data scientist的考题
【在 p*****2 的大作中提到】
:
: dict =
: 'I': true
: 'love': true
: 'you': true
:
: dfs = (str, curr, res)->
: if curr is str.length
: return console.log res.join(" ")
:
|
