leetcode

gistfile1.txt

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # dynamic programming
        products = []
        memo = {}
        for i in range(0, len(nums)):
            product = 1
            
            leftProduct = self.productBetween(nums, memo, 0, i - 1)
            rightProduct = self.productBetween(nums, memo, i + 1, len(nums) - 1)
            product = leftProduct * rightProduct
            
            #for j in range(0, len(nums)):
            #    if i != j:
            #        product = product * nums[j]
            
            products.append(product)
        return products
    
    def productBetween(self, nums, memo, start, end):
        # change memo key to tuple
        if [start, end] in memo:
            return memo[[start, end]]
        elif start < 0 or end >= len(nums):
            return 1
        elif start == end:
            return nums[start]
        else:
            product = nums[start] * self.productBetween(nums, memo, start + 1, end)
            memo[[start, end]] = product
            return product