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

---

We can use dynamic programming to solve this problem. Use split[i] to represent if until ith position of the string it can be split. When we get to (i+1)th position, we can start from 0 to check if s[j..i+1] is a word in dict. When we reach the end, we can get the result.

C++ Code:

/*
 * func: word_break
 * goal: to find out if the input string can be split into words in the dict
 * @param s: input string
 * @param dict: input dictionary
 * return: true or false
 */
/*
 * split[i] stands for if s[0..i] can be split into words in the dict
 * complexity: time O(n^2), space O(n)
 */
bool word_break(string s, unordered_set<string> &dict){
    if(s.length() ==0 || dict.size() == 0){
        return false;
    }
    vector<bool> split(s.length()+1, false);
    split[0] = true;
    for(int i = 0; i < s.length(); ++i){
        for(int j = 0; j <= i; ++j){
            string tmp_word = s.substr(j, i - j + 1);
            if(dict.find(tmp_word) != dict.end() && split[j]){
                split[i+1] = true;
            }
        }
    }
    
    return split[s.length()];
}

Python Code:

# func: determine if the input string can be split into words in the dictionary
# @param s: input string
# @param dict: input dictionary
# @return: True of False
# complexity: time O(n^2), space O(n)
def word_break(s, dict):
    if not s or not dict:
        return False
    splitable = [False] * (len(s)+1)
    splitable[0] = True
    for i in xrange(len(s)):
        for j in xrange(i+1):
            tmp_word = s[j: i+1]
            if tmp_word in dict and splitable[j-1]:
                splitable[i] = True
                break

    return splitable[-1]