Simple topdown approach ..(works for worst case without exclusive checks)


  • 0
    L
        map<int, vector<string>> cache;
    
    vector<string> wordBreak(string s, unordered_set<string>& wordDict ) {
    
    return wordBreak(s,wordDict,0);
    
    }
    
    vector<string> wordBreak(string &s, unordered_set<string>& wordDict, int spaceat) {
        
        vector<string> next;
        
        if(cache.find(spaceat) != cache.end())
            return cache[spaceat];
             
        if( spaceat == s.length())
                return cache[spaceat]=next;
    
        for( int i=spaceat ; i<s.length(); i++)
        {
            string curword = s.substr(spaceat , i-spaceat+1);
            
            if( wordDict.find( curword ) !=wordDict.end() )
            {
                 vector<string> bel= wordBreak(s,wordDict, i+1);
                 //check if this is the last suffix, else ignore
                 if( bel.size()==0 && (i+1)==s.length())
                      next.push_back(curword);
                 for( string p: bel )
                 {
                      next.push_back(curword+" "+p);
                 }
             
            }
            
        }
        return cache[spaceat]=next;
    }

Log in to reply
 

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