题目描述：

给一个字符串s，和一个字典dict，判断是否可以按照该字典，对字符串进行分词

例如s="abcabcd", dict={"abc", "abcd"}，则返回true。

 

今天心血来潮，剖析一下这道题目的思路。

一拿到这个题目，就是相到简单的深搜了，从头开始枚举所有可能的字串（枚举每一个位置，每一个位置枚举所有以此位置开始的子串，直到结束），一旦发现了合法组合立刻返回true。

于是思路出来了，代码5分钟写完，这能难住我嘛？？

word break 朴素实现代码如下：

bool wordBreakHelper(string s,int len, unordered_set
     
       &dict, int pos)    {        if (pos == len)            return true;        for (int i = 1; i <= len - pos; i++)        {            string t = s.substr(pos, i);            if (dict.find(t) != dict.end())            {                if (wordBreakHelper(s, len, dict, pos + i))                    return true;            }        }        return false;    }    bool wordBreak(string s, unordered_set
      
        &dict)    {        return wordBreakHelper(s, s.length(), dict, 0);    }
      
     

提交，Judging，Judging。。。卧槽，超时了

这个时候该思考效率问题了

对每一个子串都枚举，尽管只有子串在dict中找到才进入递归，但是复杂度仍然达到了 O( dict.size() ^ s.length() )。卧槽。

幂次还是过高。

进一步思考，深搜是没问题的，关键是搜索空间一定有许多重复的分支。每个字串最多枚举过一次，那么是哪里重复了呢？仔细推理每一次的搜索，我发觉每一次进入递归的pos参数（就是wordBreakHelper参数中的pos）就是把问题切割成为一个求s从pos开始的子串是否可以break的子问题，这样如果前面已经计算过从pos开始的子串是不可以分割的，下一次就直接无视这个分支了。。。是的，问题解决了。

我们利用一个tag数组，用以标记从pos开始的子串是否可分割。初始全部设置为true，计算过程中逐渐更新tag，每一次进入递归之前先判断tag，再决定是否进入下一步。

修改后的代码如下：

int *tag;bool wordBreakHelper(string s,int len, unordered_set
     
       &dict, int pos){    if (pos == len)        return true;    for (int i = 1; i <= len - pos; i++)    {        if (tag[pos]==1)        {            string t = s.substr(pos, i);            if (dict.find(t) != dict.end()){                if (wordBreakHelper(s, len, dict, pos + i))                    return true;                else                    tag[pos+i] = 0;            }        }    }    return false;}bool wordBreak(string s, unordered_set
      
        &dict){    tag = new int[s.length()];    fill(tag, tag + s.length(), 1);    return wordBreakHelper(s, s.length(), dict, 0);}