Can it be solved recursively ?


  • 0
    T

    My solution shows

    Time Limit Exceeded in below case

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

    Did I make some mistake?

    public bool WordBreak(string s, ISet<string> wordDict) 
    {
       if( string.IsNullOrEmpty( s ) ) return false;
       
       return wordBreakRecursive( s,wordDict );
    }
    
    private bool wordBreakRecursive( string s, ISet<string> wordDict )
    {
        for( int i = 0; i < s.Length; ++i )
        {
            if(  !wordDict.Contains( s.Substring( 0, i + 1 ) ) )continue;
            
            if( i == s.Length -1 || wordBreakRecursive( s.Substring(i+1),wordDict) )
            {
                return true;
            }
        }
        
        return false;
    }

  • 1

    The problem is that you'll call wordBreakRecursive over and over again with the same strings, and you go to work every time. For each different string, you should compute the result only once, remember it, and return it from memory if the same string is given again. See Memoization.


  • 0

Log in to reply
 

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