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

Question

这是一个面试问题.假设你有一个字符串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)

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

Answer 1

在这篇博客文章中,对此问题的解决方案有一个非常详尽的说明.

基本的想法是只记住你写的函数,你将有一个O(n ^ 2)时间,O(n)空间算法.

Answer 2

该解决方案假定字典存在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.