LeetCode 139. 单词拆分 （线性DP+字典树）

单词拆分 状态：$dp[i]$表示子串$[1,i]$能否拼成。 DP方程:$dp[i]|=dp[j]\&check(s[j+1,i])$ ，也就是说，如果一个前缀能拆分成功，再加上一个字典里的单词就都可以拆分成功。

class Trie{ struct Node{ bool end = false; Node* children[26] = {0}; }; Node* root = new Node; public: void insert(const string &s){ Node *p = root; for(char c:s){ if(!p->children[c-'a']){ p->children[c-'a'] = new Node; } p = p->children[c-'a']; } p->end = true; } bool isInTrie(const string &s,int l,int r){ Node *p = root; for(int i=l;i<=r;i++){ char c = s[i]; if(!p->children[c-'a']){ return false; } p = p->children[c-'a']; } return p->end; } }; class Solution { public: Trie trie; bool wordBreak(string s, vector<string>& vs) { for(string& s:vs){ trie.insert(s); } int m = s.size(); s = " "+s; vector<bool> dp(m+1,0); dp[0] = 1; for(int j=1;j<=m;j++){ for(int i=1;i<=j;i++){ if(dp[i-1] && trie.isInTrie(s,i,j) ){ dp[j] = true; break; } } } return dp[m]; } };