2

I am working on this problem https://leetcode.com/problems/climbing-stairs and getting an error 'global name helper is not defined'. But it is defined in the class?

class Solution(object):
    def climbStairs(self, n, ):
        """
        :type n: int
        :rtype: int
        """

        return helper(0, n)

    def helper(self, curr, n):
        if (curr > n):
            return 0

        if (curr == n):
            return 1

        return helper(curr + 1, n) + helper(curr + 2, n)
ivymatch
  • 99
  • 1
  • 6
  • 1
    It's `self.helper(...)`. And additionally unlike in Java you don't have to bundle functions in classes. – Klaus D. Aug 25 '19 at 07:01

2 Answers2

0

helper is a bound function of a Solution instance, you need to call it on self.

as per the timeout error on bigger inputs, that's because you make 2 recursive calls per call to helper, which means a runtime complexity of O(2^N).

because many of the calls are with the same arguments, you can use functools.lrucache to cache results of previous calls, which reduces it to O(N)

from functools import lru_cache

class Solution(object):
    def climbStairs(self, n, ):
        """
        :type n: int
        :rtype: int
        """

        return self.helper(0, n)

    @lru_cache()
    def helper(self, curr, n):
        if (curr > n):
            return 0

        if (curr == n):
            return 1

        return self.helper(curr + 1, n) + self.helper(curr + 2, n)


s = Solution()
print(s.climbStairs(35))
Adam.Er8
  • 12,675
  • 3
  • 26
  • 38
  • Still a run time error. When I added self to the first helper call in the climbStairs function, it's a timeout error when the input is 35. – ivymatch Aug 25 '19 at 07:03
  • @ivymatch I edited my answer with a solution to the timeout error as well – Adam.Er8 Aug 25 '19 at 07:07
0

You are missing the 'self' argument for helper i.e replacing helper() with self.helper() should hopefully work.


class Solution(object):
    def climbStairs(self, n, ):
        """
        :type n: int
        :rtype: int
        """

        return self.helper(0, n)

    def helper(self, curr, n):
        if (curr > n):
            return 0

        if (curr == n):
            return 1

        return self.helper(curr + 1, n) + self.helper(curr + 2, n)
glory9211
  • 741
  • 7
  • 18