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

1. 题意

2. 思路

具体做法是: 弄一个字典树Trie, 然后在Trie中做dfs。
dfs的定义是: dfs(string& s, int index), 表示在字符串s中开始搜索, 当前的搜索区间为 [index, s.size()),看是否能把s这个字符串在trie中搜索完

记忆化: 另外需要用个数组visist记录dfs没搜索到时对应的s中的下标, 用bool或int数组都可以。

为什么做记忆化?
如果不做记忆化, 部分test case会TLE超时, 因为不做记忆化时会有挺多的重复判断。

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];
    bool wordBreak(string s, vector<string>& wordDict) {
        Trie trie;
        bool flag = false;
        for(int i = 0 ; i < 310 ; i ++) {
            visit[i] = false;
        }
        for(string str : wordDict) {
            trie.insert(str);
        }
        function<void(int)> dfs = [&](int index) -> void{
            if(index == s.length()) {
                flag = true;
                return ;
            }
            if(visit[index]) {
                return ;
            } else {
                visit[index] = true;
            }
            Trie* p = &trie;
            for(int i = index ; i < s.length() ; i ++) {
                if(p -> children[s[i] - 'a'] != nullptr) {
                    p = p -> children[s[i] - 'a'] ;
                    if(p -> isEnd) {
                        dfs(i + 1) ;
                    }
                } else {
                    break;
                }
            }
        };
        dfs(0);
        return flag;
    }
};
int main()
{
    // cats an dog cat
    string s = "catsandogcat";
    vector<string>wordDict{"cats","dog","sand","and","cat","an"};
    Solution solution;
    int flag = solution.wordBreak(s, wordDict);
    cout<< flag << endl;
    return 0;
}