Word Segmentation

Word Segmentation

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example

Given

s = "lintcode",

dict = ["lint", "code"].

Return true because "lintcode" can be segmented as "lint code".

------------------------- thinking ---------------------------------
"", [] -> both empty, return true;
"", ["a"]->string empty, return true;
"a", []-> dict empty, return false;

optimization codes:
when dict doesn't contain all string's character, return false directly
------------------------- codes --------------------------------
class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordSegmentation(string s, unordered_set<string> &dict) {
        // write your code here
        if (s.size() < 1 && dict.size() == 0) return true;
        if (s.size() < 1) return false;
        int chrs[256] = {0};
        for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) {
            string cur = *it;
            for (int i = 0; i < cur.size(); i++) {
                chrs[cur[i]]++;
            }
        }
        for (int i = 0; i < s.size(); i++) {
            if (chrs[s[i]] == 0) {
                return false;
            }
        }
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for (int i = 0; i < s.size(); i++) {
            for (int j = i-1; j >= -1; j--) {
                if (dp[j+1] && dict.find(s.substr(j+1, i - j)) != dict.end()) {
                    dp[i+1] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};