w*********m
发帖数: 4740 | 1 不是打印所有可能的组合。只打印valid的
字典里保存的是单个的词，不是整个的词组。比如一个电话的10位数match上了abc def
ghij。
abc,def,ghij是3个不同的词。字典里保存的是abc,def,ghij是3个词，不是abcdefghij。
seems最快的办法要先给字典建prefix tree，这样才可以在扫瞄电话的过程中提前返回。
比如前2个数列举到了ab,没有任何词以ab开头，也没有任何词以b开头（虽然a在字典中
），这时就不用在往下try aba了,直接开始try ac。 |
c********p
发帖数: 1969 | |
w*********m
发帖数: 4740 | 3 总之我是被黑了。
【在 c********p 的大作中提到】
: mark
|
z****e
发帖数: 54598 | 4 题目我忘了
原题是什么？
【在 w*********m 的大作中提到】
: 总之我是被黑了。
|
w*********m
发帖数: 4740 | 5 给个电话，找其对应的有意义的英文组合
原体是所有组合
【在 z****e 的大作中提到】
: 题目我忘了
: 原题是什么？
|
c********p
发帖数: 1969 | 6 比起你，我今天才是被黑了。
【在 w*********m 的大作中提到】
: 总之我是被黑了。
|
c********p
发帖数: 1969 | 7 你能看一下你心想里我的代码么？
【在 z****e 的大作中提到】
: 题目我忘了
: 原题是什么？
|
w*********m
发帖数: 4740 | 8 没过就没啥差别，没有更黑一说。这个黑我的是个密友。上次我还头一次被国人黑了
他开始没说清楚字典只含单个词，不是全长
我是写出来了，只不过字典用的Set
他说可以early terminate，我说那得用prefix tree才行
【在 c********p 的大作中提到】
: 比起你，我今天才是被黑了。
|
|
c********p
发帖数: 1969 | 9 我先mark了，回头看看。
能告诉我哪家么？
什么是密友？
【在 w*********m 的大作中提到】
: 没过就没啥差别，没有更黑一说。这个黑我的是个密友。上次我还头一次被国人黑了
: 他开始没说清楚字典只含单个词，不是全长
: 我是写出来了，只不过字典用的Set
: 他说可以early terminate，我说那得用prefix tree才行
|
z****e
发帖数: 54598 | 10 可以hash干掉duplication呀，set不是对了么？
【在 w*********m 的大作中提到】
: 没过就没啥差别，没有更黑一说。这个黑我的是个密友。上次我还头一次被国人黑了
: 他开始没说清楚字典只含单个词，不是全长
: 我是写出来了，只不过字典用的Set
: 他说可以early terminate，我说那得用prefix tree才行
|
|
|
z****e
发帖数: 54598 | 11 先找到所有可能的组合，这个跟前题一致
然后打印valid的时候需要查找
查找效率最高的不是tree，就是hashcode
字典里面，26个字母只要固定下来
hashcode可以直接编出不碰撞的code
取java缺省的prime=31就好了
都不需要override hashcode方法
这样查找效率可以实现o(1)
我觉得一开始你说set是对的
【在 w*********m 的大作中提到】
: 不是打印所有可能的组合。只打印valid的
: 字典里保存的是单个的词，不是整个的词组。比如一个电话的10位数match上了abc def
: ghij。
: abc,def,ghij是3个不同的词。字典里保存的是abc,def,ghij是3个词，不是abcdefghij。
: seems最快的办法要先给字典建prefix tree，这样才可以在扫瞄电话的过程中提前返回。
: 比如前2个数列举到了ab,没有任何词以ab开头，也没有任何词以b开头（虽然a在字典中
: ），这时就不用在往下try aba了,直接开始try ac。
|
w*********m
发帖数: 4740 | 12 他最后要的是还没把一个组合完全找出来就提前back
比如才看到前3个字母
【在 z****e 的大作中提到】
: 先找到所有可能的组合，这个跟前题一致
: 然后打印valid的时候需要查找
: 查找效率最高的不是tree，就是hashcode
: 字典里面，26个字母只要固定下来
: hashcode可以直接编出不碰撞的code
: 取java缺省的prime=31就好了
: 都不需要override hashcode方法
: 这样查找效率可以实现o(1)
: 我觉得一开始你说set是对的
|
w*********m
发帖数: 4740 | 13 你说的是啥duplication？
【在 z****e 的大作中提到】
: 可以hash干掉duplication呀，set不是对了么？
|
w*********m
发帖数: 4740 | 14 你这到底啥意思？
比如最后的一个组合是 get bank atm
字典中有get，bank和atm，但没有getbankatm
你这个咋搞？
【在 z****e 的大作中提到】
: 先找到所有可能的组合，这个跟前题一致
: 然后打印valid的时候需要查找
: 查找效率最高的不是tree，就是hashcode
: 字典里面，26个字母只要固定下来
: hashcode可以直接编出不碰撞的code
: 取java缺省的prime=31就好了
: 都不需要override hashcode方法
: 这样查找效率可以实现o(1)
: 我觉得一开始你说set是对的
|
z****e
发帖数: 54598 | 15 那就变成切割题
给你一个string，快速判断，切割开来的小块
是不是valid string
结合前面的，外加递归和dfs
我依稀记得leetcode上有类似的题目
【在 w*********m 的大作中提到】
: 你这到底啥意思？
: 比如最后的一个组合是 get bank atm
: 字典中有get，bank和atm，但没有getbankatm
: 你这个咋搞？
|
w*********m
发帖数: 4740 | 16 对呀。我就这么实现的。先找到一个完全长的string，再recursive地try所有cut的方
式，有一种成功就提前返回true。
结果他要求在找到完全长的string前就提前结束，如果不可能。
那就只能用prefix tree了
【在 z****e 的大作中提到】
: 那就变成切割题
: 给你一个string，快速判断，切割开来的小块
: 是不是valid string
: 结合前面的，外加递归和dfs
: 我依稀记得leetcode上有类似的题目
|
z****e
发帖数: 54598 | 17 递归＋dfs不就可以了
【在 w*********m 的大作中提到】
: 对呀。我就这么实现的。先找到一个完全长的string，再recursive地try所有cut的方
: 式，有一种成功就提前返回true。
: 结果他要求在找到完全长的string前就提前结束，如果不可能。
: 那就只能用prefix tree了
|
z****e
发帖数: 54598 | 18 它的意思不用bfs，用dfs吧？
hashcode还是要用的
【在 w*********m 的大作中提到】
: 对呀。我就这么实现的。先找到一个完全长的string，再recursive地try所有cut的方
: 式，有一种成功就提前返回true。
: 结果他要求在找到完全长的string前就提前结束，如果不可能。
: 那就只能用prefix tree了
|
w*********m
发帖数: 4740 | 19 你怎么还是没明白
如果字典是一个HashSet，一共要两个dfs递归
第一个dfs递归用全部数字递归找一个对应的string
在得到这个string后，调用第二个dfs递归把这个string递归分割，去字典了看每个分
割出的词是不是都存在
他要求在第一个递归里尽量不要递归到全部数字就返回，如果发现这条路走不通
【在 z****e 的大作中提到】
: 递归＋dfs不就可以了
|
z****e
发帖数: 54598 | 20 也就是要合并两个递归？
【在 w*********m 的大作中提到】
: 你怎么还是没明白
: 如果字典是一个HashSet，一共要两个dfs递归
: 第一个dfs递归用全部数字递归找一个对应的string
: 在得到这个string后，调用第二个dfs递归把这个string递归分割，去字典了看每个分
: 割出的词是不是都存在
: 他要求在第一个递归里尽量不要递归到全部数字就返回，如果发现这条路走不通
|
|
|
w*********m
发帖数: 4740 | 21 可以这么说。但是没法简单合并。第二个递归必须要try所有的segmentations，都不对
，才不对。但在第一个递归里，你还没拿到全长的string，只看见部分的string，这部
分的string的全部segmentations都不在字典里也不能说明这条路不对，因为再加一个
字母就有可能在字典里了
所以我说得用prefix tree才能在看到部分string时能决定是不是在字典里
但我写了两个递归之后，时间已经差不多了，我就讲了idea，他也没让我写prefix
tree。但我感觉99%他会给坏评价了
【在 z****e 的大作中提到】
: 也就是要合并两个递归？
|
j*******r
发帖数: 201 | 22 The better solution:
1. preprocess the dictionary:
Traverse all valid words in the dictionary,
build a hashmap with key=digit, value = a set of valid words with the same
digit
2. When receive the digit input, search the hashmap to get all valid words.
Complexity: O(1)
def
abcdefghij。
回。
【在 w*********m 的大作中提到】
: 不是打印所有可能的组合。只打印valid的
: 字典里保存的是单个的词，不是整个的词组。比如一个电话的10位数match上了abc def
: ghij。
: abc,def,ghij是3个不同的词。字典里保存的是abc,def,ghij是3个词，不是abcdefghij。
: seems最快的办法要先给字典建prefix tree，这样才可以在扫瞄电话的过程中提前返回。
: 比如前2个数列举到了ab,没有任何词以ab开头，也没有任何词以b开头（虽然a在字典中
: ），这时就不用在往下try aba了,直接开始try ac。
|
w*********m
发帖数: 4740 | 23 这个我也提了，不过不是他要的答案
当然也许他要的答案就是你没有写成code的那个
【在 j*******r 的大作中提到】
: The better solution:
: 1. preprocess the dictionary:
: Traverse all valid words in the dictionary,
: build a hashmap with key=digit, value = a set of valid words with the same
: digit
: 2. When receive the digit input, search the hashmap to get all valid words.
: Complexity: O(1)
:
: def
: abcdefghij。
|
w*********m
发帖数: 4740 | 24 还有就是，要达到O(1)
就得把字典里能组合成10位电话的所有词对应的数字全部组合一遍，不便宜的
【在 j*******r 的大作中提到】
: The better solution:
: 1. preprocess the dictionary:
: Traverse all valid words in the dictionary,
: build a hashmap with key=digit, value = a set of valid words with the same
: digit
: 2. When receive the digit input, search the hashmap to get all valid words.
: Complexity: O(1)
:
: def
: abcdefghij。
|
