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

思路

字符串处理的一个题目，首先想到的办法就是穷举：从头开始找N-letter word，查一下在不在字典里呗。但是纯穷举的话显然就会超时，因为这个问题可以分解成下面的子问题，即给定字符串s及起始位置start，寻找s[start…end]能不能够被拆分。这个子问题在暴力搜索的时候很容易被重复，所以得找个东西记录一下状态，碰到相同的子问题就不用再去查字典了。
所以，他是个动态规划的题。

代码

bool wordBreakSub(const string& s, unordered_set<string>& wordDict, int startPos, int* memory)
{
    if(memory[startPos] != -1)
        return memory[startPos]!= 0;
    string subStr;
    bool canBreak = false;
    for(int len=1; len <= s.size() - startPos; len++)
    {
        subStr = s.substr(startPos, len);
        if(wordDict.count(subStr) > 0) {
            if (startPos + len == s.size()) {
                memory[startPos] = 1;
                return true;
            }
            canBreak = wordBreakSub(s, wordDict, startPos + len, memory);
        }
        if(canBreak)
            break;
    }
    memory[startPos] = canBreak ? 1 : 0;
    return canBreak;
}
bool wordBreak(string s, unordered_set<string>& wordDict)
{
    int* memory = new int[s.size()];
    for(int i=0; i<s.size(); i++)
        memory[i] = -1; //-1:untest; 0-false; 1-true
    return wordBreakSub(s, wordDict, 0, memory);
}