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

This problem is easy while using Dynamic Programming. The first time I tried was failed. If you find the existed words in sequence the following data should be failed:
s = "aaaaaaa"
dict = ["aaa", "aaaa"]. Because what you found would be aaa aaa a and return a false. 

Algorithm:
1. Find the problem and subproblem and their relations.
2. Build a table[n][n], and table[0][n] would be the result we return.
3. table[i][j] = true iff s.substr(i, j-i+1) is in the dict OR for every i<=k<=j, 
   table[i][k]&&table[k+1][j] is true.

Tips:
while your final result is depend on table[0][n], you should make length as the out-most loop control.

My Code:
bool wordBreak(string s, unordered_set<string> &dict) {
        int n = s.length();
        bool table[n][n];
        memset(table, 0, sizeof(table));
        for(int len = 0; len < n; len++){
            for(int i = 0; i < n-len; i++){
                int j = i + len;
                table[i][j] = (dict.find(s.substr(i, j-i+1)) == dict.end() ? false:true);
                if(!table[i][j]){
                    for(int k = i; k < j; k++){
                        if(table[i][k] && table[k+1][j]){
                        table[i][j] = true;
                        break;
                        }
                    }
                }
            }
        }
        return table[0][n-1];
    }

=============================================================================

Better Solution with O(n^2) space and time complexity.

My code:

 bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.empty() || dict.empty()) return false;
        int n = s.length();
        bool table[n];
        memset(table, 0, sizeof(table));
        for(int i = 0; i < n; i ++){
            if(dict.find(s.substr(0, i+1)) != dict.end()) {
                table[i] = true;
                continue;
            }
            for(int j = 0; j < i ; j++){
                if(table[j] && dict.find(s.substr(j+1, i-j)) != dict.end()){
                    table[i] = true;
                    break;
                }
            }
        }
        return table[n-1];
    }