C++ both top-down and bottom-up


  • 0
    X
    class Solution {
    public:
        //DP bottom-up
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            if(wordDict.empty() || (s == "" && wordDict.find(s) == wordDict.end())){
                return false;
            }
            int len = s.length();
            vector<bool> dp(len + 1, false);
            dp[0] = true;
            for(int i = 1; i <= len; ++i){
                for(int j = 1; j <= i; ++j){
                    string tmp = s.substr(j -  1, i - j + 1);
                    if(dp[j - 1] && wordDict.find(tmp) != wordDict.end()){
                        dp[i] = true;
                    }
                }
            }
            return dp[len];
        }
        //DP top-down solution
        /*
        unordered_map<int, bool> m;
        bool dfs(int p, string s, unordered_set<string>& wordDict){
            if(p == s.length()){
                return true;
            }
            if(m.find(p) != m.end()){
                return m[p];
            }
            m[p] = false;
            for(int i = p; i < s.length(); ++i){
                string tmp = s.substr(p, i - p + 1);
                if(wordDict.find(tmp) == wordDict.end()){
                    continue;
                }
                bool b = dfs(i + 1, s, wordDict);
                m[i + 1] = b;
                if(m[i + 1]){
                    m[p] = true;
                    break;
                }
            }
            return m[p];
        }
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            if(wordDict.empty() || (s == "" && wordDict.find(s) == wordDict.end())){
                return false;
            }
            return dfs(0, s, wordDict);
        }
        */
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.