Clean non-recursive solution


  • 0
    S
    class Solution(object):
        def numTrees(self, n):
            """
            :type n: int
            :rtype: int
            """
            table = [1,1]
            for i in xrange(2, n+1):
                table.append(sum(table[leftSize]*table[i-1-leftSize]\
                            for leftSize in xrange(0, i)))
            return table[n]
    

    It's fast, though I know it's not difficult to find the actually formula of each node.


  • 0
    D
    This post is deleted!

  • 0
    D
    This post is deleted!

  • 0
    D

    It is a nice solution. I tried 3 times this solution, the best run time is 40ms & 44.02%. I make "table" a global parameter to speed up, now I got 36ms run time.

    table = [1,1]
    class Solution(object):
        def numTrees(self, n):
            """
            :type n: int
            :rtype: int
            """
            global table
            try:
                return table[n]
            except IndexError:
                for i in xrange(len(table), n+1):
                    table.append(sum(table[leftSize]*table[i-1-leftSize]\
                                     for leftSize in xrange(0, i)))
                return table[n]

Log in to reply
 

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