Leetcode test system doesn't seem consistent


  • 0
    Q

    For Concatenated Words, I chose to use Trie instead of hash table because I thought that using hash table may require slicing each word many times. I submitted my Trie implementation several times and got different result. First, I got TLE on test 14/43, but when I "run code" with that test, I got correct answer in 72ms. Then I resubmitted, and got memory limit exceeded on the test ["a", "aa", "aaa"...."aaa...a"]. But when I clicked to see more detail, I was shown that 43/43 test passed. And I copied the test and "run code" again, and I got correct answer.

    0_1482038784056_mle.png

    Similarly, in the Matchsticks to Square problem, my recursion solution got TLE on the test [10,10,5,4,9,1,9,4,10,5,4,6,10,1,3], yet when I "run code" with that test, the runtime was only 32ms:

    0_1482038948417_TLE.png

    I suspect this inconsistency costs other contestants many time during the contest too.

    Lastly, I guess my code isn't optimal so I hope that someone can give me advice on improving my Trie implementation. Thanks in advance!

    class Node(object):
        def __init__(self, val = -1):
            self.val = -1
            self.next = {}
    
    class Solution(object):
        def findAllConcatenatedWordsInADict(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            n = len(words)
            if n == 0: return []
            
            root = Node()
            
            t = sorted(range(n), key = lambda i: len(words[i]))
            #print t
            
            res = []
            for i in range(n):
                word = words[t[i]]
                if len(word) == 0: continue
            
                pos = [0]
                count = [0]
                
                concatenated = False
                
                while pos and not concatenated:
                    k = pos.pop()
                    c = count.pop()
                    
                    cur = root
                    while True:
                        if not word[k] in cur.next: break
                    
                        cur = cur.next[word[k]]
                        k += 1
                        
                        if k == len(word):
                            if cur.val != -1:
                                concatenated = c >= 1
                            break
    
                        if cur.val != -1:
                            pos.append(k)
                            count.append(c+1)
                
                if concatenated:
                    res.append(word)
                else:
                    cur = root
                    for w in word:
                        if w not in cur.next:
                            cur.next[w] = Node()
                        cur = cur.next[w]
                        
                    cur.val = i
                        
            return res
    

  • 1
    T

    Same for me. Curious why this is the case.


  • 1

    Hi @quanhoang and @tcui

    Thanks for your feedback.

    LeetCode uses total test case running time as the basis for juding time complexity.

    So, even if you could pass one specific test case as you said, you will still get TLE when running into this test case, since you have already accumulated lots of running time before you begin to run this test case.

    About the problem of MLE, we are working on this problem. We have raised up the Python's code Memory limit before the contest, but there are still some of Python users got MLE, sorry for your inconvenience.

    Best,
    LeetCode Team


  • 0
    A
    This post is deleted!

  • 0
    T

    Hi @love_FDU_llp
    Thank you for your reply. Could you please add this testcase in the system? ["a"*50000+"b", "a"]


  • 0

    @quanhoang Your solution for Concatenated Words now get accepted.


Log in to reply
 

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