https://leetcode-cn.com/problems/word-break-ii/

1. 题意

2. 思路

构建一个trie树，然后在树上搜索单词，搜索成功就记下来

3. 题解

#include<bits/stdc++.h>
using namespace std;
class Trie {
public:
    vector<Trie*>children;
    int num;
    bool isEnd;
    char ch;
    Trie* searchPrefix(string prefix){
        Trie* node = this;
        for(char ch : prefix) {
            ch = ch - 'a';
            if(node -> children[ch] == nullptr) {
                return nullptr;
            }
            node = node -> children[ch];
        }
        return node;
    }
    Trie() : children(26),num(0),isEnd(false){}
    void insert(string word) {
        Trie* node = this;
        for(char ch : word) {
            ch -= 'a';
            if(node -> children[ch] == nullptr) {
                node -> children[ch] = new Trie;
            }
            node = node -> children[ch];
            node -> ch = ch + 'a';
        }
        node -> num = (node -> num) ++;
        node -> isEnd = true;
    }
    bool search(string word) {
        Trie* trie = this -> searchPrefix(word);
        return trie == nullptr ? false : trie -> isEnd;
    }
    bool startsWith(string prefix) {
        Trie* trie = this -> searchPrefix(prefix);
        return trie == nullptr ? false : true;
    }
};
class Solution {
public:
    bool visit[310];
    vector<string>  wordBreak(string s, vector<string>& wordDict) {
        Trie trie;
        vector<string> vec;
        for(int i = 0 ; i < 310 ; i ++) {
            visit[i] = false;
        }
        for(string str : wordDict) {
            trie.insert(str);
        }
        function<void(int,string)> dfs = [&](int index,string str) -> void{
            if(index == s.length()) {
                vec.push_back(str);
            }
            Trie* p = &trie;
            string temp;
            for(int i = index ; i < s.length() ; i ++) {
                if(p -> children[s[i] - 'a'] != nullptr) {
                    p = p -> children[s[i] - 'a'] ;
                    temp.push_back(s[i]);
                    if(p -> isEnd) {
                        if(str.size() != 0 && str.substr(str.size() -1) != " ") {
                            //注意这里有肯能多加空格，要判断一下加过空格不用在添加
                            str += " ";
                        }
                        dfs(i + 1,str + temp) ;
                    }
                } else {
                    break;
                }
            }
        };
        dfs(0,"");
        return vec;
    }
};
int main()
{
    //此例子如狗不多加空格判断会，会出现错误
    string s = "pineapplepenapple";
    vector<string>wordDict{"apple","pen","applepen","pine","pineapple"};
    Solution solution;
    vector<string> vec = solution.wordBreak(s,wordDict);
    for(auto it : vec) {
        cout<< it <<endl;
    }
    return 0;
}