单词拆分I/II(字典树/dp)

单词拆分（字典树）

题目：https://leetcode-cn.com/problems/word-break/ 代码：https://leetcode-cn.com/problems/word-break-ii/solution/dong-tai-gui-hua-qian-zhui-shu-by-scut_dell/

class Solution {
public:
    
    class Node {
    public:
        Node* next[26];
        bool has_word;
        Node() {
            has_word = false;
            for(int i = 0;i next[c - 'a']) {
                root->next[c - 'a'] = new Node();
            }
            root = root->next[c - 'a'];
        }
        root->has_word = true;
    }
    
    void collect(string &s, vector &next, int idx, string now, vector &ret) {
        if (idx == s.size()) {
            now.pop_back();
            ret.push_back(now);
            return;
        }
        for (auto p: next[idx]) {
            collect(s, next, p + 1, now + s.substr(idx, p + 1 - idx) + " ", ret);
        }
    }
    
    bool wordBreak(string s, vector& wordDict) {
        Node* root = new Node();
        for (auto word: wordDict) {
            insert(root, word);
        }
        
        vector match(s.size() + 1, false);
        vector next(s.size(), vector());
        
        match[s.size()] = true;
        
        for (int i = s.size() - 1;i >= 0;i--) {
            Node* t = root;
            for (int j = i;j next[s[j] - 'a']) {
                    t = t->next[s[j] - 'a'];
                    if (t->has_word && match[j + 1]) {
                        next[i].push_back(j);
                    }
                } else {
                    break;
                }
            }
            if (next[i].size() > 0) {
                match[i] = true;
            }
        }
        return match[0];       
        // vector ret;
        // if (!match[0]) {
        //     return ret;
        // } else {
        //     collect(s, next, 0, "", ret);
        //     return ret;
        // }
    }
};

单词拆分II（dp）

题目：https://leetcode-cn.com/problems/word-break-ii/ 代码：https://leetcode-cn.com/problems/word-break-ii/solution/140-by-ikaruga/

class Solution {
public:
	vector wordBreak(string s, vector& wordDict)
	{
		if (!wordBreak_139(s, wordDict)) return {};

		size_t validEnd = 0;
		vector dp(s.size() + 1, vector());

		for (size_t i = 0; i  s.size()) continue;
				if (memcmp(&s[i], &word[0], word.size()) != 0) continue;
				validEnd = max(validEnd, newEnd);
				if (i == 0)
				{
					dp[newEnd].push_back(word);
					continue;
				}
				for (auto& d : dp[i])
				{
					dp[newEnd].push_back(d + " " + word);
				}
			}
		}

		return dp.back();
	}
};