gistfile1.cpp

bool wordBreak(string s, unordered_set<string> &dict) {
    int len = s.length();
    if(len==0) return true;
    if((len == 1) &&(dict.find(s)!=dict.end())) 
        return true;
    else if(len == 1)
        return false;

    int *DPB = new int[len+1];  //DPB[i]=true: substr (start from 0, length=i) breakable, find DPB[len]
    for(int i=0; i<=len; i++)
        DPB[i] = false;
    DPB[0] = true;
    DPB[1] = (dict.find(s.substr(0,1)) != dict.end());

    for(int i=1; i<s.length(); i++)
    {
        for(int j=i; j>=0; j--)
        {
            string sub = s.substr(j, i-j+1);
            if((dict.find(sub)!=dict.end()) && DPB[j])
            {
                DPB[i+1]=true;
                break;
            }
        }
    }
    bool res = DPB[len];
    delete []DPB;
    return res;
}

Solution2

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
        vector<bool> dp(len + 1,false);
        dp[len] = true;

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                string str = s.substr(i,j - i + 1);
                if (dict.find(str) != dict.end() && dp[j + 1]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
};