How to optimize recursive DP solution?


  • 0
    K

    class Solution {
    public:

    unordered_map<string,bool> mp;
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(mp.find(s)!=mp.end())
            return mp[s];
        for(int i=1;i<s.size();i++)
        {
            string s1=s.substr(0,i);
            string s2=s.substr(i);
            if(wordDict.find(s1)!=wordDict.end()&&wordDict.find(s2)!=wordDict.end()||wordBreak(s1,wordDict)&&wordBreak(s2,wordDict))
                return mp[s]=true;
        }
        if(wordDict.find(s)!=wordDict.end())
                return mp[s]=true;
        return mp[s]=false;
    }
    

    };


Log in to reply
 

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