如何将给定文本分解为字典中的单词？

这是一道面试题。假设你有一个字符串text and a dictionary（一组字符串）。你如何崩溃text成子串，使得每个子串都可以在dictionary.

例如你可以分解"thisisatext" into ["this", "is", "a", "text"] using /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)
  

是否有意义？您会优化在字典中搜索前缀的步骤吗？您会推荐哪些数据结构？

该解决方案假设字典存在 Trie 数据结构。进一步，对于Trie中的每个节点，假设以下功能：

1. node.IsWord() ：如果该节点的路径是单词，则返回 true
2. node.IsChild(char x)：如果存在标签为 x 的子节点，则返回 true
3. 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 是字典中最长单词的长度。

PS：我假设字典中有以下单词：this，is，a，text，ate。