Can't we use recursion?


  • 1
    Y

    something like:

      bool wordBreak(string &s, unordered_set<string> &dict) {
    
                    if( wordBreak( s.substr(i,len-i), dict ) ){
                        return true;
                    }
    
    }
    

    full code here:

    #define F(i, a, b) for(int i = a; i <= b; i++)
    
        class Solution {
        public:
            //bool 
    
        bool wordBreak(string &s, unordered_set<string> &dict) {
            int len = s.size();
    
            F(i, 1, len){
                if( dict.find( s.substr(0,i) ) != dict.end() ){
    				if( i == len ){
    					return true;
    				}
                    if( wordBreak( s.substr(i,len-i), dict ) ){
                        return true;
                    }
                }
            }
    
            return false;
        }
    };
    

    I would like to get a TLE before moving to DP or something.


  • 0
    Y

    the exact reason still remains unknown, yet this bit of change could get it work:

    			string tmp = s.substr(i);
                if( wordBreak( tmp, dict ) ){

Log in to reply
 

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