LeetCode139：Word Break

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

/*
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.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".
*/ 
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.size() == 0 || dict.size() == 0)
            return false;
        int len = s.size();
        vector<bool> dp(len+1, false);//保存状态，dp[i]表示前i个字符是否可以进行wordBread 
        dp[0] = true;
        for(int i = 1; i <= len; i++)
            for(int j = 0; j < i; j++)
            {
                if(dp[j] && dict.count(s.substr(j, i-j)) == 1)//对前i个字符进行切分时，只要有一种情况为true，则dp[i]=true 
                {
                    dp[i] = true;
                    break;
                }
            }
        return dp[len];
        
    }
    
    bool wordBreak2(string s, unordered_set<string> &dict) {
        if(s.size() == 0 || dict.size() == 0)
            return false;
        int len = s.size();
        vector<bool> dp(len+1, false);//保存状态，dp[i]表示前i个字符是否可以进行wordBread 
        dp[0] = true;
        for(int i = 0; i < len; i++)
            if(dp[i])
            {
                for(int j = 1; j <= len-i; j++)
                    if(dict.count(s.substr(i, j)) == 1)
                        dp[i+j] = true;
            }

        return dp[len];
        
    }
    

};

int main(void)
{
    string s("leetcode");
    unordered_set<string> dict;
    dict.insert("leet");
    dict.insert("code");
    Solution solution;
    bool ret = solution.wordBreak(s, dict);
    cout<<ret<<endl;

    return 0;
}