C++ 9ms using memoization, easy to understand


  • 0
    B

    using a map to store the result of string start with index (key)
    using another set to store the failed index to avoid redundant examination

    the code is ugly but efficient

    class Solution {
    public:
        unordered_map<int,vector<string>> ans;
        unordered_set<int> tried;
        int minLen = INT_MAX;
        int maxLen = 0;
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) 
        {
    
            for(auto e : wordDict)
            {
                minLen = min(minLen, (int)e.length());
                maxLen = max(maxLen, (int)e.length());
            }
            help(s,0,wordDict);
            return ans[0];
        }
        
        bool help(string & s, int pos, unordered_set<string>& wordDict)
        {
            if(pos==s.length() || ans.find(pos)!=ans.end() ) return true;
            if(tried.find(pos)!=tried.end()) return false;
            vector<string>result;
            for(int i = minLen; i<= maxLen && i+pos<=s.length();i++)
            {
                string str = s.substr(pos,i);
                if(wordDict.find(str)!=wordDict.end() && help(s,pos+i,wordDict))
                {
                    if(ans[pos+i].empty())
                        result.push_back(str);
                    else
                        for(auto e : ans[pos+i])
                            result.push_back(str+" "+e);
                }
            }
            if(result.empty())
            {
                tried.insert(pos);
                return false;
            }
            ans[pos]=result;
            return true;
        }
    };

Log in to reply
 

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