[Leetcode]118 : Pascal’s Triangle

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

Problem :
Given an integer numRows, return the first numRows of Pascal's triangle.

圖來自leetcode

圖來自leetcode

Thoughts :
1. numRows是從1一開始。
2. 每一行的第一個跟最後一個數字都是1
3. 每一行的第 i 個值為 i-1 行第 j-1個加上 i-1 行第 j 個的值

Solution :

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # i是行、j是列
        result = []
        for i in range(numRows):
            result.append([])
            for j in range(i+1):
                # 如果j是第一個或是最後一個，直接append 1
                if j in (0,i):
                    result[i].append(1)
                else:
                    result[i].append(result[i-1][j-1]+result[i-1][j])
        return result

Time complexity = O(n²)(?, space complexity?