23.03.16 Today’s Leetcode

106. Construct Binary Tree from Inorder and Postorder Traversal (medium)

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        if len(postorder) == 1:
            return TreeNode(postorder[0])
        node = TreeNode(postorder[-1])
        index = inorder.index(postorder[-1])
        node.left = self.buildTree(inorder[:index], postorder[:index])
        node.right = self.buildTree(inorder[index + 1:], postorder[index:-1])
        return node

349. Intersection of Two Arrays (easy)

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))
        

304. Range Sum Query 2D - Immutable (medium)

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.board = [[0 for i in range(n)] for j in range(m)]
        self.board[0][0] = 0
        for i in range(m):
            for j in range(n):
                if j - 1 >= 0:
                    self.board[i][j] += self.board[i][j - 1]
                if i - 1 >= 0:
                    self.board[i][j] += self.board[i - 1][j]
                if i - 1 >= 0 and j - 1 >= 0:
                    self.board[i][j] -= self.board[i - 1][j - 1]
                self.board[i][j] += matrix[i][j]
        # print(self.board)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = self.board[row2][col2]
        if row1 - 1 >= 0: res -= self.board[row1 - 1][col2]
        if col1 - 1 >= 0: res -= self.board[row2][col1 - 1]
        if row1 - 1 >= 0 and col1 - 1 >= 0: res += self.board[row1 - 1][col1 - 1]
        return res


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

306. Additive Number (medium)

Iterative Approach

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        
        # check if the sequence is valid starting from the first two numbers
        for i in range(1, n):
            for j in range(i + 1, n):
                # if the first two numbers have leading zeros, move on to the next iteration
                if num[0] == "0" and i > 1:
                    break
                if num[i] == "0" and j > i+1:
                    break
                    
                # initialize the first two numbers and check if the sequence is valid
                num1 = int(num[:i])
                num2 = int(num[i:j])
                k = j
                while k < n:
                    # calculate the next number in the sequence and check if it matches the remaining string
                    num3 = num1 + num2
                    if num[k:].startswith(str(num3)):
                        k += len(str(num3))
                        num1 = num2
                        num2 = num3
                    else:
                        break
                if k == n:
                    return True
                
        # if no valid sequence is found, return False
        return False

DFS Approach

class Solution(object):
    # According to:
    # https://leetcode.com/discuss/70089/python-solution
    # The key point is choose first two number then recursively check.
    # DFS: recursice implement.
    def isAdditiveNumber(self, num):
        length = len(num)
        for i in range(1, length/2+1):
            for j in range(1, (length-i)/2 + 1):
                first, second, others = num[:i], num[i:i+j], num[i+j:]
                if self.isValid(first, second, others):
                    return True
        return False

    def isValid(self, first, second, others):
        # Numbers in the additive sequence cannot have leading zeros,
        if ((len(first) > 1 and first[0] == "0") or
                (len(second) > 1 and second[0] == "0")):
            return False
        sum_str = str(int(first) + int(second))
        if sum_str == others:
            return True
        elif others.startswith(sum_str):
            return self.isValid(second, sum_str, others[len(sum_str):])
        else:
            return False