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

http://www.lintcode.com/en/problem/word-break/

Discussion

Very classical DP.
f[i] is true means sub-string [0,i] can be segmented. f[i] = true when [0,i] belongs to dictionary or existing a j,0<=j<i, f[j]&&[j+1, i] belongs to dictionary.

Solution

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.length();
        vector<bool> f(n, false);
        if(n==0) return true;
        string sub = s.substr(0,1);
        if(wordDict.find(sub) != wordDict.end())
            f[0] = true;
        else
            f[0] = false;
        for(int i=1; i<n; i++) {
            if( wordDict.find(s.substr(0, i+1)) != wordDict.end()) {
                f[i] = true;//先判断[0,i]是不是属于dictionary，是的话就不用找j了。如果先找j，找不到的时候再判断效率低很多。
                continue;
            }
            for(int j=i-1; j>=0; j--) {
                if(f[j] && wordDict.find(s.substr(j+1, i-j)) != wordDict.end()) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n-1];
    }
};

上面的solution在leetcode上accepted，但是在lintcode上time limited。。。
时间复杂度O(n^2)，空间复杂度O(n)

Solution 2

利用字典里面的单词的最大长度（假设为M），可以将复杂度降低为O(Mn)。

用f[i]表示前i个字符能break，代码更好写。

class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordBreak(string s, unordered_set<string> &dict) {
        // write your code here
        if(s.length()==0 ) return true;
        int n = s.length();
        vector<bool> f(n+1, false);
        f[0] = true;
        int maxLen = 0;
        for(unordered_set<string>::iterator it = dict.begin(); it!=dict.end(); it++) {
            int tmp = (*it).length();
            if(tmp > maxLen) {
                maxLen = tmp;
            }
        }
        for(int i=1; i<=n; i++) {
            for(int j=i-1; j>=0; j--) {//这里一定要自底向上才行
                if(i-j> maxLen) {//这里降低复杂度，利用maxLen
                    break;
                }
                if(f[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }
};

Solution 3 DFS

这个题也可以用DFS实现，每个单词哪里要么break要么不break，根据ABCD画出状态转移图，起始就是个有向图。问题转换成有向图中路径是否存在问题。关键在于找一个节点的neighbors怎么找。O(2^n)复杂度，提交超时。

//O(2^n) rumtime
class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.length()==0 && dict.empty()) return true;
        if(s.length() == 0) return false;
        return breakable(s, dict, 0);

    }
    //start is the starting positoin of next level, it's also the length of the path
    bool breakable(string s, unordered_set<string> &dict, int start) {
        int n = s.length();
        if(start == n) return true;
        vector<string> words = GetNeighbors(s, start, dict);
        for(auto const& word : words) {
            if(breakable(s, dict, start+word.length())) {
                return true;
            }
        }
        return false;

    }
    //return all the substrings staring from pos
    vector<string> GetNeighbors(string s, int pos, unordered_set<string> &dict) {
        vector<string> result;
        string sub;
        for(int i=pos; i<s.length(); i++) {
            sub.append(1, s[i]);
            if(dict.find(sub) != dict.end())
                result.emplace_back(sub);
        }
        return result;
    }
};

每个单词哪里要么break要么不break，这个思路在String Palindrome那个题里面也是一样的，所以DFS的思路也可以一样. 上面说状态转移图是个有向图，起始更严格的说是个树

class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.empty()) return true;
        int n = s.length();
        return isBreakable(s, 0, dict);
    }
    bool isBreakable(string s, int pos, unordered_set<string> &dict) {
        if(pos == s.length()) {
            return true;
        }
        for(int i=pos; i<s.length(); i++) {
            if(dict.find(s.substr(pos, i-pos+1)) == dict.end()) {
                continue;
            }
            if(isBreakable(s, i+1, dict)) {
                return true;
            }
        }
        return false;
    }
};