139. Word Break

• Difficulty: Medium

• Topics: Dynamic Programming

• Similar Questions:

  • Word Break II

Problem:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Solutions:

class Solution {
public:
    struct TrieNode{
        bool stop;
        TrieNode* next[26];
        TrieNode(bool stop = false) {
            this->stop = stop;
            for (int i = 0; i < 26; ++i) {
                next[i] = nullptr;
            }
        }
    };

    class Trie {
        public:
            Trie() {
                root = new TrieNode();
                cur = root;
            }

            TrieNode* getCur() {
                return cur;
            }

            void setCur(TrieNode* cur) {
                this->cur = cur;
            }

            void rewind() {
                cur = root;
            }

            bool next(char c) {
                if (cur == nullptr || cur->next[c - 'a'] == nullptr) {
                    cur = nullptr;
                    return false;
                }

                cur = cur->next[c - 'a'];
                return true;
            }

            bool isWord() {
                return cur->stop;
            }

            void input(string s) {
                cur = root;
                for (auto c : s) {
                    if (cur->next[c - 'a'] == nullptr) {
                        cur->next[c - 'a'] = new TrieNode();
                    }
                    cur = cur->next[c - 'a'];
                }
                cur->stop = true;
                cur = root;
            }
        private:
            TrieNode* root;
            TrieNode* cur;
    };


    bool wordBreak(string s, vector<string>& wordDict) {
        Trie trie;
        for (auto word : wordDict) {
            trie.input(word);
        }

        unordered_map<int, bool> cache;

        return helper(s, 0, trie, cache);
    }

    bool helper(const string& s, int pos, Trie& trie, unordered_map<int, bool>& cache) {
        if (pos == s.length())  return true;
        if (cache.count(pos) > 0)   return cache[pos];
        for (int i = pos; i < s.length(); ++i) {
            if (trie.next(s[i]) == false) {
                cache[pos] = false;
                return false;
            } else {
                if (trie.isWord()) {
                    TrieNode* cur = trie.getCur();
                    trie.rewind();
                    if (helper(s, i + 1, trie, cache)) {
                        cache[pos] = true;
                        return true;
                    }
                    trie.setCur(cur);
                }
            }
        }
        cache[pos] = false;
        return false;
    }


};