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

// Given a string s and a dictionary of strings wordDict, return true if s can be
// segmented into a space-separated sequence of one or more dictionary words.

// Note that the same word in the dictionary may be reused multiple times in the
// segmentation.

////////////////////////////////////////////////////////////////////////////////

// ans depending on prev -> dp
// dp[i] = if can break using s[0...i]
// to update dp[i], check if s[j...i] is word (use hashMap) and dp[j-1] == true
// speed up: stop when len(s[j...i]) > max_word_len
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int maxLen = 0;
        unordered_set<string> words;
        for (const auto& word : wordDict) {
            maxLen = max(maxLen, (int)word.size());
            words.insert(word);
        }
        
        int n = s.size();
        vector<bool> dp(n, false);
        for (int i = 0; i < n; ++i) {
            for (int j = i; j >= 0 && i - j + 1 <= maxLen; --j) {
                string word = s.substr(j, i - j + 1); // s[j...i]
                if (j - 1 >= 0 && !dp[j - 1]) continue; // dp[j-1] == false
                if (words.find(word) == words.end()) continue; // not a word
                dp[i] = true; break;
            }
        }
        return dp.back();
    }
};
