Python with DFS


  • 4
    K

    Accepted python code with DFS (1073ms):

        def lexicalOrder(self, n):
            def dfs(k, res):
                if k <= n:
                    res.append(k)
                    t = 10*k
                    if t <= n:
                        for i in range(10):
                            dfs(t + i, res)
            res = []
            for i in range(1, 10):
                dfs(i, res)
            return res
    

    Interestingly, with only one modification to the above code, the following code gets Memory Limit Exceeded.

        def lexicalOrder(self, n):
            def dfs(k):
                if k <= n:
                    res.append(k)
                    t = 10*k
                    if t <= n:
                        for i in range(10):
                            dfs(t + i)
            res = []
            for i in range(1, 10):
                dfs(i)
            return res
    

    The only difference between these two is that, in the latter one, we do not pass the list res as an argument to the function dfs. Can anybody explain this phenomenon? Thanks!


  • 2

    I don't have a full explanation for the Memory Limit Exceeded, but I experimented a bit and...

    • I also get MLE for it every time.
    • I get it accepted every time when I do gc.collect() at the start of lexicalOrder. So apparently the problem is leftovers from previous runs and the garbage collection just isn't eager enough.
    • I also always get it accepted if I instead set dfs = None before returning.
    • I tried del dfs, but that caused Runtime Error. Trying it locally, I see that it's SyntaxError: can not delete variable 'dfs' referenced in nested scope. Providing the function to itself via parameter like def dfs(k, dfs): solves that problem, and then del dfs is allowed and the solution gets accepted.
    • Turns out the def dfs(k, dfs): thing is enough, I then also get it accepted without del dfs.

  • 0

    Forgot to talk about the difference... So apparently the dfs function in the second version is somewhat harder to delete and thus might stick around longer. Since it references the res entry in the outer scope, I guess the list then has to stick around longer as well. The first version on the other hand doesn't access the outer scope but accesses res via a local variable, which dies when dfs returns. So that might be the crucial difference.


  • 0
    K

    @StefanPochmann Thanks for your explanation. Very informative!


  • 0
    C

    I just notice another problem, if I change

        for i in range(10):
    

    to

        for i in range(0,10):
    

    it will be time limited exceed . . . and I am still trying to find out the reason


  • 0

    @chuncao said in Python with DFS:

    it will be time limited exceed

    I submitted that twice, it was accepted and just as fast as without the zero. Are you sure you got "Time Limit Exceeded", not a similar-sounding result?


  • 0
    C

    @StefanPochmann Oh I find out the reason is that my original code is not efficient compared with kejin's solution. The code like this will not pass

        class Solution(object):
            def lexicalOrder(self,n):
                """
                :type n: int
                :rtype: List[int]
                """
                result = []
                def regress(i,result):
                    
                    if i<=n:
                        result.append(i)
                    for j in range(0,10):
                        if i*10 + j <= n:
                            regress(i*10 + j,result)
                        else:
                            return
                for i in range(1, 10):
                    regress(i,result)
                    
                return result
    

    until I change it to

        class Solution(object):
            def lexicalOrder(self,n):
                """
                :type n: int
                :rtype: List[int]
                """
                def regress(i,result):
                    
                    if i<=n:
                        result.append(i)
                    if i*10 <= n:
                        for j in range(0,10):
                            if i*10 + j <= n:
                                regress(i*10 + j,result)
                            else:
                                return
                result = []
        
                for i in range(1, 10):
                    regress(i,result)
                    
                return result
    

    It has nothing to do with range(10) and range(0,10). "range(10)" only helped me get accepted once yesterday( I don't know why ) but does not work today.


  • 0
    L

    I have similar TLE problem, and @chuncao 's solution help me fix the TLE. But I still don't understand why the first version gets TLE.
    My first version is :

    class Solution(object):
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        self.result = []
        self.helper(0, 1, n)
        return self.result
    def helper(self, base, level, n):
        for i in range(0, 10):
            if level == 1 and i == 0: 
                continue
            thisNum = base * 10 + i
            if thisNum > n:
                return
            self.result.append(thisNum)
            if level < len(str(n)):
                self.helper(base * 10 + i, level + 1, n)
    

    My accepted version is :

    class Solution(object):
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        self.result = []
        self.helper(0, 1, n)
        return self.result
    
    def helper(self, base, level, n):
        if base*10 > n:
            return
        for i in xrange(0, 10):
            if level == 1 and i == 0: 
                continue
            thisNum = base * 10 + i
            if thisNum > n:
                return
            self.result.append(thisNum)
            self.helper(base * 10 + i, level + 1, n)
    

    Why the second version is faster than the first one for large number? Thanks!


Log in to reply
 

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