139. Word Break

解題思路

零錢問題的字串版(?)

要用 hashMap 來存已經看過的節省時間，不然就 TLE。

程式碼

class Solution {
public:
    unordered_map<string, bool> mp;
    bool helper(string s, vector<string>& wordDict)
    {
        if(mp.count(s))
            return mp[s];
        if(s == "")
            return true;
        for(int i=0; i<wordDict.size(); i++)
        {
            if(s.rfind(wordDict[i], 0) == 0)
            {
                if(helper(s.substr(wordDict[i].size()), wordDict))
                {
                    mp[s] = true;
                    return true;
                }
            }
        }
        mp[s] = false;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        return helper(s, wordDict);
    }
};