[LeetCode] Word Break

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".

Analysis:

Use DP to indicate whether some part of the string is composed by the words in the dictionary.

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

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