DFS 4ms treak solution


  • 0
    K
    int n;
    unordered_map< char, bool > m;
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(s.size() == 0)return true;
      
        if(!n){
            for(auto x: wordDict){
                n = max(n,(int)x.size());
                for(auto z : x )
                    m[z] = true;
            }
            for(int i = 0;i<s.size();i++)
                if(m.find(s[i]) == m.end())
                    return false;
        }
        
        for(int i = min(n,(int) s.size()); i >= 0; i--)
            if(wordDict.find(s.substr(s.size() - i)) != wordDict.end() 
               && wordBreak(s.substr(0,s.size() - i ),wordDict))
                return true;
            
        
        return false;
        
    }

Log in to reply
 

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