Why can this simple code be accepted?


  • 0
    G

    My own code exceeds time limit and I run the Last executed input on my computer which takes about 3~4 seconds. Then I found the following code which is accepted. The strange thing is I run this program on the same test case and it took about 10 seconds.

    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 == end:
                return 1
        
            all_chars = map(chr, xrange(ord('a'), ord('z') + 1))
            visited = set()
            bfs = [start, None]
            
            # at which distance the following to-be-processed nodes are
            distance = 2
            
            while len(bfs) > 1:
                word = bfs.pop(0)
                if word is None:
                    distance += 1
                    bfs.append(None)
                    continue
                
                for i in xrange(len(word)):
                    for char in all_chars:
                        new_word = word[:i] + char + word[i + 1:]
                        if new_word == end:
                            return distance
                        if new_word in dict and new_word not in visited:
                            bfs.append(new_word)
                            visited.add(new_word)
        
            return 0
    

    And here below is my code. My TLE solution works way faster than the code above on my own computer, but I don't know why it turns out to be slow on the OJ system.

    # -*- coding:utf-8 -*-
    
    # Return True if the two strings have one different character
    def oneDiff(stra, strb):
    	count = 0
    	for i in range(len(stra)):
    		if stra[i] != strb[i]:
    			count += 1
    		if count > 1:
    			return False
    	if count != 1:
    		return False
    	return True
    
    # Binary search
    # Return True if samp is in dic
    def isIn(samp, dic, first=None, last=None):
    	if first == None:
    		first = 0
    	if last == None:
    		last = len(dic) - 1
    	if first > last:
    		return False
    	m = (first + last) / 2
    	if samp == dic[m]:
    		return True
    	elif samp < dic[m]:
    		return isIn(samp, dic, first, m-1)
    	else:
    		return isIn(samp, dic, m+1, last)
    
    # Generate a list of words that are one character different with sample
    def diffList(sample):
    	alist = []
    	for i in range(len(sample)):
    		c = ord(sample[i]) - 97
    		for j in range(26):
    			if j != c:
    				mtstr = sample[:i] + chr(j + 97) + sample[i+1:]
    				alist.append(mtstr)
    	return alist
    	
    class Solution:
    	# @param start, a string
    	# @param end, a string
    	# @param dict, a set of string
    	# @return an integer
    	def ladderLength(self, start, end, dic):
    		dic = sorted(dic)				# sort the dictionary
    		path = collections.deque()		
    		visit = set()
    
    		for it in diffList(start):		# put the starting points into the queue
    			if isIn(it,dic):
    				path.appendleft([it, 2])
    				visit.add(it)
    
    		while len(path) > 0:			# 
    			[midway, distence] = path.pop()
    			if oneDiff(midway, end):
    				return distence + 1
    			for item in diffList(midway):
    				if item in visit or not isIn(item,dic):
    					continue
    				else:
    					path.appendleft([item, distence+1])
    					visit.add(item)
    		return 0
    

    This is the test case which I failed on.
    http://www.mediafire.com/view/l6i4favodvmkibe/testcase.txt


  • 0
    Q

    dict is a 'set' object, and when you call 'item in dict', it will be searched by hash table, which is faster (O(1)) than binary search (O(log n)).

    BTW, there are so many function calls of chr() and list.append() in your diffList() function. But in the simple code, he predefine the 'all_chars' list and use 'for each' in every while loop, which is faster.


Log in to reply
 

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