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!