题目：

给定字符串，以及一个字典，判断字符串是否能够拆分为 字典中的单词。例如：字典为{Hello，World}，给定字符串为HelloHelloWorld，则可以拆分为Hello，Hello，World，都是字典中的单词。

分析：

这样的题目叫做“分词问题”，有点勉强。只是这是自然语言处理，搜索引擎领域中，非常基础的一个问题，解决的方法比较多，相对也比较熟悉，但这仍旧是一个值的探索的问题。那我们从简单的题目入手，看看如何处理题目中的问题。最直接的思路就是递归，很简单，我们考虑每一个前缀，是否在字典中？如果在，则递归剩下的字串，如果不在，则考虑其他前缀。

public boolean wordBreak(String str)    {        int size = str.length();        if(size == 0)            return true;        //考虑所有的前缀        for(int i=1;i <= size;i++)        {            //如果前缀在字典中，则递归处理后缀            if(trie.fullMatch(str.substring(0, i)) && wordBreak(str.substring(i,size)))                return true;        }        return false;    }

在上面的代码中，每一种情况都要处理字串，程序耗时较长，不可接受。那么如何改进呢？

答案是：在递归子问题中，找重复子问题。这个题的重复子问题很明显：如下图表示。

所以，通过动态规划的方法，可以有较大的幅度提升。用一个二重循环，时间复杂度能够提升到O（n²）。

//优化的分词问题动态规划求解        public boolean wordBreakDP(String str)    {        int size = str.length();        if(size == 0)            return true;        //如果字串sub(0,i)能够分词，则wb[i] = true        boolean [] wb = new boolean [size+1];        for(int i=0;i<size + 1;i++)        {            wb[i] = false;        }        for(int i = 1; i <= size ;i++)        {                        if(wb[i] == false && trie.fullMatch(str.substring(0,i)))            {                wb[i] = true;            }            if(wb[i] == true)            {                if(i == size)                {                    return true;                }                for(int j = i+1;j<=size;j++)                {                    if(wb[j] == false && trie.fullMatch(str.substring(i,j)))                    {                        wb[j] = true;                    }                    if(j == size && wb[j] == true)                    {                        return true;                    }                }            }        }        return false;    }

除了上述两个方法以外，这个问题的解法有很多！

分词问题