如何将给定的文本分解成字典中的单词？
这是一个面试问题。假设你有一个字符串text和一个dictionary（一组字符串）。你如何分解text成子字符串，以便在每个子字符串中找到dictionary。
例如，你可以分解"thisisatext"成["this", "is", "a", "text"]使用/usr/share/dict/words。
我相信回溯可以解决这个问题（在伪Java中）：
void solve(String s, Set<String> dict, List<String> solution) {
if (s.length == 0)
return
for each prefix of s found in dict
solve(s without prefix, dict, solution + prefix)
}
List<String> solution = new List<String>()
solve(text, dict, solution)
是否有意义？你会优化在词典中搜索前缀的步骤吗？你会推荐什么样的数据结构？
回答 2
Stack Overflow用户
发布于 2018-04-27 14:56:41
该解决方案假设字典中存在Trie数据结构。此外，对于Trie中的每个节点，都承担以下功能：
- node.IsWord（）：如果该节点的路径是一个单词，则返回true
- node.IsChild（char x）：如果存在具有标签x的子项，则返回true
- node.GetChild（char x）：返回带有标签x的子节点
Function annotate( String str, int start, int end, int root[], TrieNode node): i = start while i<=end: if node.IsChild ( str[i]): node = node.GetChild( str[i] ) if node.IsWord(): root[i+1] = start i+=1 else: break;end = len(str)-1 root = [-1 for i in range(len(str)+1)] for start= 0:end: if start = 0 or root[start]>=0: annotate(str, start, end, root, trieRoot)index 0 1 2 3 4 5 6 7 8 9 10 11 str: t h i s i s a t e x t root: -1 -1 -1 -1 0 -1 4 6 -1 6 -1 7
我将留下部分给你，通过反向遍历根来列出构成字符串的单词。
时间复杂度是O（nk），其中n是字符串的长度，k是字典中最长单词的长度。
Stack Overflow用户
发布于 2018-04-27 16:06:26
对于这个问题的解决方案，这里有一个非常彻底的书面说明。博客帖子。
基本思想是你写的函数，你将有一个O(n^2)时间，O(N)空间算法。
https://stackoverflow.com/questions/-100008287
复制相似问题