题目描述：
?
给一个字符串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);
}