c++ memorizing dfs


  • 0
    N
    class Solution {
    private:
        unordered_set<string> fail;
        bool dfs(string s, unordered_set<string>& wordDict) {
            if (s.length() == 0)
                return true;
            for (int i = 1; i <= s.length(); i++) {
                string a = s.substr(0, i);
                
                if (wordDict.find(a) != wordDict.end()) {
                    string after = s.substr(i);
                    if (fail.find(after) == fail.end()) {
                        if (dfs(after, wordDict))
                            return true;
                        else
                            fail.insert(after);
                    }
                }
            }
            
            return false;
        }
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            return dfs(s, wordDict);
        }
    };
    

Log in to reply
 

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