j********3
发帖数: 33 | 1 convert keypad numbers to all possible words.
input: str. return: list of string
for example:
'8474833' -> [ ['VISITED'], ['THRIVED'], ... ]
问时间复杂度：exponential time.O(3^n) or O(4^n)
follow up 1：返回list of breakable words.
for instance:
'3278227' -> [ ['FAST','CAR'], ['DART', 'BAR'], ['EAR', 'TABS'], ... ]
时间来不及了，没来得及做。应该就是dfs+backtracking.
follow up 2: 如何优化。答 用prefix/trie
不出意外 基本是挂了，之前没做过这题，确实有点生疏。
其实并不难。 | j******o
发帖数: 4219 | | e**********0
发帖数: 502 | 3
现在bar真是高
【在 j********3 的大作中提到】
: convert keypad numbers to all possible words.
: input: str. return: list of string
: for example:
: '8474833' -> [ ['VISITED'], ['THRIVED'], ... ]
: 问时间复杂度：exponential time.O(3^n) or O(4^n)
: follow up 1：返回list of breakable words.
: for instance:
: '3278227' -> [ ['FAST','CAR'], ['DART', 'BAR'], ['EAR', 'TABS'], ... ]
: 时间来不及了，没来得及做。应该就是dfs+backtracking.
: follow up 2: 如何优化。答 用prefix/trie
| l***4
发帖数: 1788 | 4 followup是word break吧 应该是dp
【在 j********3 的大作中提到】
: convert keypad numbers to all possible words.
: input: str. return: list of string
: for example:
: '8474833' -> [ ['VISITED'], ['THRIVED'], ... ]
: 问时间复杂度：exponential time.O(3^n) or O(4^n)
: follow up 1：返回list of breakable words.
: for instance:
: '3278227' -> [ ['FAST','CAR'], ['DART', 'BAR'], ['EAR', 'TABS'], ... ]
: 时间来不及了，没来得及做。应该就是dfs+backtracking.
: follow up 2: 如何优化。答 用prefix/trie
| j********3
发帖数: 33 | 5
当然。。。。否则就dfs所有路径。根本没难度了
【在 j******o 的大作中提到】
: 你得有字典吧
| j********3
发帖数: 33 | 6
如果当作是word break，那要对每一条dfs路径 再做word break
这样解法效率太低。
我觉得用dp＋backtracking, 然后把dictionary转成prefix tree
【在 l***4 的大作中提到】
: followup是word break吧 应该是dp
| s******7
发帖数: 1758 | 7 dfs + trie 店面有点难了，时间估计不太够，可能followup说说思路就行了 |
|
