单词切分（LintCode）

给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

样例
给出

s = "lintcode"

dict = ["lint","code"]

返回 true 因为"lintcode"可以被空格切分成"lint code"

第一种DP算法，时间复杂度高

class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> dp = vector<bool>(s.size()+1,false);
        dp[0] = true;
        for(int i = 1; i<s.size()+1;i++) {
            for(int j = 0; j < i;j++) {
                if(dp[j] == true && dict.count(s.substr(j,i-j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

• 假设s(j,i)表示j到i的字符串
  第一种思路是dp[i]表示s(0,i)的字符串可以被空格分切成字典中的单词
  状态转移方程则为dp[i] = dp[j] && (s(j,i)是否存在字典中)
• 第二种DP优化思路是算出字典中长度最长的字符串，i-j的长度不可能超过最大长度

第二种DP优化算法，时间复杂度稍微优化

class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> dp = vector<bool>(s.size()+1,false);
        int maxL = getMaxLength(dict);
        dp[0] = true;
        for(int i = 1; i<s.size()+1;i++) {
            for(int j = i; j >= 1 && j >= (i-maxL);j--) {
                if(dp[j-1] == true && dict.count(s.substr(j-1,i-j+1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }

    int getMaxLength(unordered_set<string> &dict) {
        int maxLength = 0;
        for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) { 
            maxLength = maxLength > (*it).length() ? maxLength : (*it).length();
        }
        return maxLength;
    }
};