[WORD BREAK II] "Time Limit Exceeded" error when input is "a", []


  • 3
    S

    Why always I get "Time Limit Exceeded" error when input is "a", [].
    In my opinion, if input is "a", [], the function should return immediately.
    And if I use dict==[] for the judgement, the result is False, it is very strange to me.....

     class Solution:
        	def wordBreak(self, s, dict):
        		if len(dict) == 0:
        			return []
        		else:
        			return self.subwordBreak(s, dict)
        
        	def subwordBreak(self, s, dict):
        		if len(s) == 1 and s not in dict:
        			return []
        		retStrList = []
        		length = len(s)
        
        		for i in range(0, length+1):
        			if s[:i] in dict:
        				if s[i:] in dict:
        					retStrList.append(s[:i] + " " + s[i:])
        				elif s[i:] == '':
        					retStrList.append(s[:i])
        				else:
        					subStrList = self.subwordBreak(s[i:], dict)
        					for item in subStrList:
        						retStrList.append(s[:i] + " " + item)
        		return retStrList

  • 1
    1

    I also got that problem.
    The "a,[]" test case could return successfully when I use Eclipse to run my java code on my computer.
    Cannot figure out why...


  • 1
    S

    I think the error reporting system is not working correctly for python and java, it must be some cases like
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"] that make your code TLE.

    For your algorithm to be accepted, you need to modify it to use some cache to store results of subproblems that may happen repeatedly. Or you could just use dp which should be O(M*N).


  • 0
    D

    Actually, my non-recursive DP got time exceeded error while recursive accepted. Both are implemented by python. However, I believe what you said is the case.


Log in to reply
 

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