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

Most of problems that return a bool value or int value (amount) in LeetCode can be solved using Dynamic Programming.

We can define something named “record(a, b)”, which means the sub-string start from a and has b length can be constructed with words in dictionary. Here’s an example.

find “karanokyoukai” in this dictionary: (空の境界)

“ka“, “o“, “anok“, “ok“, “kai“, “no“, “kala“, “ran“, “you“, “kyou“.

Using Dynamic Programming, we can get this record:

 

For example, we can see in first ‘k’ row, the ‘2’ column is TRUE, because we can find “ka” word in dictionary; for same reason, in first ‘k’ row, the ‘7’ column is TRUE, because we can find “ka”, “ran”, “ok” in dictionary.

Then all we need to do is to check the value of record(0, len), it is 1, that means the sub-string which start from 0, and have len length, can be broken to elements in dictionary.

    bool wordBreak(string s, unordered_set<string> &dict) {
        int length = s.size();
        bool **record = new bool*[length];
        for(int i=0; i < length; i++){
            record[i] = new bool[length];
        }
        for(int i = 0; i < length; i ++){
            for(int j = 0; j < length; j++){
                record[i][j] = false;
            }
        }
        for(int i = 0; i < length; ++ i){
            for(int len = 0; len < length - i; ++ len){
                string subword = s.substr(i,len + 1);
                if(dict.find(subword) != dict.end()){
                    record[i][len] = true;
                    if(i > 0 && record[0][i - 1]){
                        record[0][i + len] = true;  
                    } 
                }
            }
        }
        return record[0][length - 1];
    }

🙂