讨论/求职面试/大神给解答一个算法题-用java语言/
大神给解答一个算法题-用java语言

实现函数f(_str, _set)。它有两个参数_str和_set,_str是一个由纯小写字母组成的字符串,_set是一个集合(set),里面放着所有的英语单词,都是纯小写字母形式。要求f返回一个列表,它的每一个元素都是一个英语单词,并且把它们按顺序连接起来,就是_str.

例如:
_set= set(['a', 'app', 'apple', 'desk', 'top', 'led'])
f('appledesktop', _set) 会返回['apple', 'desk', 'top']
f('appledappleatop', _set) 会返回['app', 'led', 'apple', 'a', 'top']

共 2 个回复

构建字典树后用双指针遍历一次_str就好了啊。

我想了一种时间复杂度比较差的做法,
首先得到集合中所有单词的最大长度,maxLen,dfs每层尝试取当前字符串的前缀,最长的前缀检查长度为maxLen
每层尝试当前所有可能的前缀,检查是否在单词集合中,如果是的话,比如当前检查的前缀为apple,以apple后的字符串继续dfs查找,直到整个字符串查找完成

(还可以加上字典树结构维护单词集合中的所有前缀,以确定当前dfs的前缀之后是否还有可能与集合中单词匹配,做一个简单的剪枝优化