Word Break

Problem

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

You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique.

Examples

Example 1:

Input: s = "neetcode", wordDict = ["neet","code"]

Output: true

Explanation: Return true because “neetcode” can be split into “neet” and “code”.

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen","ape"]

Output: true

Explanation: Return true because “applepenapple” can be split into “apple”, “pen” and “apple”. Notice that we can reuse words and also not use all the words.

Example 3:

Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]

Output: false

Constraints

• 1 <= s.length <= 200
• 1 <= wordDict.length <= 100
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.

You should aim for a solution as good or better than O(n * m * t) time and O(n) space, where n is the length of the string s, m is the number of words in wordDict, and t is the maximum length of any word in wordDict.

Solution

DFS is checking if s[start:] can be segmented into a sequence of dictionary words. The inner loop tries every possible next word starting at start. There may be exponential ways to check some suffix, so we store results to reuse.

class Solution {
public:
    bool wordBreak(const string &s, const vector<string>& wordDict) {
        std::unordered_set<std::string_view> word_dict;
        word_dict.reserve(wordDict.size());
        
        std::size_t max_len = 0;
        for (const auto &word : wordDict) {
            max_len = std::max(max_len, word.size());
            word_dict.insert(word);
        }
 
        // memo[s.size()] is the empty string which is always true
        // -1 = unknown, 0 = false, 1 = true
        std::vector<int> memo(s.size() + 1, -1);
        memo[s.size()] = 1;
        std::string_view sv{s};
 
        std::function<bool(int)> dfs;
        dfs = [&](int start) -> bool {
            if (memo[start] != -1) {
                return memo[start] == 1;
            }
 
            // Search forward for possible words
            for (std::size_t len = 1; len <= max_len && start + len <= s.size(); ++len) {
                std::string_view candidate = sv.substr(start, len);
                // Next possible word found, recurse
                if (word_dict.contains(candidate)) {
                    if (dfs(start + len)) {
                        memo[start] = 1;
                        return true;
                    }
                }
            }
            memo[start] = 0;
            return false;
        };
        return dfs(0);
    }
};