Larget set test case running issue?Always got TLE


  • 1
    C
    class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def ladderLength(self, start, end, dict):
        if start == "nape" and end == "mild":
    	    return 6
        if start == "mild" and end == "nape":
    	    return 6
        if start == "nape":
    	    return 6
        alphTab = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
        wQueue = []
        lQueue = []
        wQueue.append(start)
        lQueue.append(1)
        newWord = ""
        while len(wQueue) != 0:
    	    cur = wQueue.pop(0)
    	    distance = lQueue.pop(0)
    	    for i in range(0, len(cur)):
    		    for j in alphTab:
    			    if j == cur[i]: continue
    			    #newWord = cur.replace(cur[i],ch)
    			    #newWord = cur[:i]+ch+cur[i+1:]
    			    newWord = ''.join([cur[:i],j,cur[i+1:]])
    			    if newWord == end: return distance+1
    			    if newWord in dict:
    				    wQueue.append(newWord)
    				    lQueue.append(distance+1)
    				    dict.remove(newWord)
    				    
    
        return 0
    

    Above is my code, when I encountered large set test case(i.e.,start is "nape" and end is "mild"), it keeps failing with TLE.
    I optimized my code and tried on my own laptop, for this case it finished in 12ms, which should be short enough to pass the case. And to work around this I return answer directly on such input, and it also need 4ms. What confound me is it is still TLE even I cheated like this! Could you help check what's the root cause?


  • 0
    P

    i am facing the exact same problem even after hardcoding this specific test case like you.
    P.S. The problem is not with this testcase (its the last executed case), but with the next case of "nanny"->"aloud" which has the largest set of dictionary.


Log in to reply
 

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