Word Break

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

Solution: Dynamic Programming

We first create a bool array, arr[i] represents whether prefix to the ith char can be segmented. If we have all the info from 0...i-1, how can we solve i?

For all suffix ending with ith char, check if suffix is in dictionary. If it does s[j..i], then we also need to check if prefix s[0..j] is also in dictionary. If both suffix and prefix are in the dictionary, then we mark arr[i] as true.

Time Complexity: O(n^2) Space Complexity: O(n)

    bool wordBreak(string &s, unordered_set<string> &dict) {
        // write your code here
        int len = s.size();
        vector<bool> res(len + 1, false);
        res[0] = true;
        for (int i = 0; i < len + 1; ++i) {
            for (int j = 0; j < i; ++j) {
                if (res[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    res[i] = true;
                    break;
                }
            }
        }
        return res[len];
    }

Solution: Recursive

We consider each prefix and search it in the dictionary. If the prefix is present in dictionary, we recur for rest of the string. If the recursive call for suffix returns true, we return true. Otherwise we try next prefix. If we have tried all prefixes and none of them resulted in any solution, we return false;

    bool wordBreak(string s, vector<string>& wordDict) {
        if (s.size() == 0) return true;

        for (int i=1; i<=s.size(); i++) {
            bool found = false;
            for (auto word: wordDict) {
                if (word == s.substr(0, i)) {
                    found = true;
                    break;
                }
            }

            if (found && wordBreak(s.substr(i, s.size()-i+1), wordDict)) {
                return true;
            }
        }

        return false;
    }