Leetcode 118. Pascal's Triangle

https://leetcode.com/problems/pascals-triangle/

Solutions are many, while the main thought is similar: generate array based on the former one.

Solution:

# T:O(n^2) S:O(n)
class Solution:
    # @param {integer} numRows
    # @return {integer[][]}
    def generate(self, numRows):
        ret = [[1], [1, 1]]
        if numRows == 0:
            return []
        elif numRows == 1:
            return [[1]]
        elif numRows == 2:
            return [[1], [1, 1]]
        else:
            for i in xrange(1, numRows - 1):
                tmp = []
                for j in xrange(len(ret[i])-1):
                    tmp.append(ret[i][j]+ret[i][j+1])
                ret.append([1]+tmp+[1])
            return ret

Run Time: 40 ms