吴波昂赛

请问楼主能说一下“一个字典和一个字符串S”的思路吗？ 用字典创建一个Trie之后， 怎么找到最长的单词呢？ 谢谢！

wangzhe890703 发表于 2017-11-26 14:41
请问楼主能说一下“一个字典和一个字符串S”的思路吗？ 用字典创建一个Trie之后， 怎么找到最长的单词呢？  ...

trie我理解，不太理解dfs什么意思。我感觉对于S的每一个i, 开始prefix 搜索。完了再从S[i+1]开始

leetcodeguy 发表于 2017-12-29 12:26
trie我理解，不太理解dfs什么意思。我感觉对于S的每一个i, 开始prefix 搜索。完了再从S开始

楼主是不是要表达Search这个method用的是类似DFS？

leetcodeguy 发表于 2017-12-29 12:26
trie我理解，不太理解dfs什么意思。我感觉对于S的每一个i, 开始prefix 搜索。完了再从S开始

我的理解是 1) build Trie based on dict 2) build freq hashmap base on String 3) do DFS in trie based on freq map. 比如string是 ababaa, a:3 b:2, dict: aaa, bb 那么比较长的是aaa