139. 单词拆分

题目：

思考：

1. 其实最先想到的是前缀树
2. 前缀树难就难在怎么回溯
3. 代码需要优化

实现：

class PreTree
{
private:PreTree* next[26];bool isEnd;public:PreTree(){isEnd = false;for (int i = 0; i < 26; i++){next[i] = nullptr;}}void insert(string word){PreTree* cur = this;for (int i = 0; i < word.size(); i++){if (cur->next[word[i] - 'a'] == nullptr){cur->next[word[i] - 'a'] = new PreTree();}cur = cur->next[word[i] - 'a'];}cur->isEnd = true;}bool search(string word){bool word_end=false;int end_pos=0;bool flag = true;PreTree* cur = this;for (int i = 0; i < word.size(); i++){if ((cur->next[word[i] - 'a'] == nullptr))    {if (!cur->isEnd){if (word_end){i=end_pos;word_end = false;}else{flag= false;break;}}cur = this;i--;}else{if (cur->isEnd){word_end = true;end_pos = i;}cur = cur->next[word[i] - 'a'];}if (i==word.size()-1){if (!cur->isEnd){if (word_end){cur=this;i=end_pos-1;word_end=false;}else{flag=false;}}}}return flag;}
};class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {PreTree* root = new PreTree();for (auto word:wordDict){root->insert(word);}return root->search(s);}
};

解释：

1. 前缀树建树过程不赘述
2. 需要额外注意访问到的前缀树的前缀中是否包含了一个完整的单词：比如{“a”,“aaa”},当前缀树走到aa时注意已经包含了一个完整的“单词（word）”：“a”。这种情况需要额外讨论以及回溯，因为查询aa时，前缀树给出的结果是aa不是一个完整词，但其实aa可以用两个“a”单词组成，这种情况得回溯到前缀树的“a”单词，同样的，s的访问也需要回到相应的位置。