CongranLu

Question115 Distinct subsequences

Link:

Code:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        IndexDict = dict()
        M = len(s)
        N = len(t)
        def UniqueSubsequence(i,j):
            if (i,j) in IndexDict:
                return IndexDict[i,j]
            else:
                if i == M or j == N or M-i<N-j:
                    return int(j == N)
                else:
                    if (i,j) in IndexDict:
                        return IndexDict[i,j]
                    else:
                        ans = UniqueSubsequence(i+1,j)
                        if s[i] == t[j]:
                            ans += UniqueSubsequence(i+1,j+1)
                        IndexDict[i,j] = ans
                        return ans
        
                        
                        
        return UniqueSubsequence(0,0)

Question 576 Out of Boundary Paths

Link:

https://leetcode.com/problems/out-of-boundary-paths/

My Code:

class Solution:
    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
        Total = 0
        NumberMat = []
        for k in range(m):
            NumberMat.append([0]*n)
        NumberMat[i][j] = 1
        if m !=1 and n!=1:
            for k in range(N):
                for row in range(m):
                    if row == 0:
                        Total += sum(NumberMat[row])+NumberMat[row][0] + NumberMat[row][-1]
                    elif row == (m-1):
                        Total += sum(NumberMat[row])+NumberMat[row][0] + NumberMat[row][-1]
                    else:
                        Total =Total + NumberMat[row][0] + NumberMat[row][-1]
                NewMat = []
                for row in range(m):
                    NewList = []
                    for col in range(n):
                        if row == 0:
                            if col == 0:
                                NewValue = NumberMat[row+1][col]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                            elif col == (n-1):
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]
                                NewList.append(NewValue)
                            else:
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                        elif row == (m-1):
                            if col == 0:
                                NewValue = NumberMat[row-1][col]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                            elif col == (n-1):
                                NewValue =  NumberMat[row-1][col]+NumberMat[row][col-1]
                                NewList.append(NewValue)
                            else:
                                NewValue =  NumberMat[row-1][col]+NumberMat[row][col-1]+NumberMat[row][col+1]
                                NewList.append(NewValue)
                        else:
                            if col == 0:
                                NewValue = NumberMat[row+1][col]+NumberMat[row][col+1]+NumberMat[row-1][col]
                                NewList.append(NewValue)
                            elif col == (n-1):
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]+NumberMat[row-1][col]
                                NewList.append(NewValue)
                            else:
                                NewValue =  NumberMat[row+1][col]+NumberMat[row][col-1]+NumberMat[row][col+1]+NumberMat[row-1][col]
                                NewList.append(NewValue)

                    NewMat.append(NewList)
                NumberMat = NewMat


            return Total%(10**9+7)
        elif m ==1 and n!=1:
            for k in range(N):
                Total += 2*sum(NumberMat[0])+NumberMat[0][0] + NumberMat[0][-1]
                NewMat = []
                NewList = []
                for col in range(n):
                    if col == 0:
                        NewValue = NumberMat[0][col+1]
                        NewList.append(NewValue)
                    elif col == (n-1):

Explanation:

The DP array is defined as the number of paths that can reach ith row , jth col in the kth step. Then we just need to iterate with the number k until n-1. For each entry of the matrix, there are three situations: in the corner, on the side and others. For either case, we take the sum of all cells next to it as the value at that cell. For each time, we sum the possible out path( all value of cells on the boarder). Then we return the result of the total value.

Question 1423. Maximum Points You Can Obtain from Cards

Link

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

My Code:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if k>= len(cardPoints):
            return sum(cardPoints)
        else:
            RestLength = len(cardPoints) - k
            TotalSum = sum(cardPoints)
            PartSum = sum(cardPoints[0:RestLength])
            Min =PartSum
            for new in range(RestLength,len(cardPoints)):
                old = new -RestLength
                PartSum= PartSum - cardPoints[old]+cardPoints[new]
                Min = min(Min,PartSum)
            return TotalSum - Min

Explanation: The idea is clear , no matter which side you choose, the list left must be continuous and the length is total length – k. Then we just need to write an iteration to calculate minimum of the list. Notice that if we use sum function here, it will exceed time limit as sum function also originates from the iteration.

Question 1048. Longest String Chain

Link:

https://leetcode.com/problems/longest-string-chain/

My Code:

class Solution:
    def longestStrChain(self, words: List[str]) -> int:

        def PredCheck(OldString, NewString):
            if len(OldString) != (len(NewString)-1):
                return False
            else:
                for j in range(len(NewString)):
                    CheckStr = NewString[0:j]+NewString[j+1:len(NewString)]
                    if CheckStr == OldString:
                        return True
                return False
        
        #We need to sort the string list based on the length of the strings in the list
        #for i in range(1,len(words)):
           # NewList = []
          #  for j in range(len(words)):
         #       NewString = words[j]
        #        Max = 0
       #         for k in range(len(words)):
      #              OldString = words[k]
     #               if PredCheck(OldString,NewString):
    #                    Max = max(ResultList[i-1][k], Max)
   #             Value = Max+1
  #              NewList.append(Value)
 #           ResultList.append(NewList)
#        return max(ResultList[-1])
        
        NewWords = sorted(words,key = len)
        ResultList = [1]
        for i in range(1,len(NewWords)):
            NewString = NewWords[i]
            Max = 0
            for j in range(i):
                OldString = NewWords[j]
                if PredCheck(OldString,NewString):
                    Max = max(ResultList[j],Max)
            Value = Max+1
            ResultList.append(Value)
        return max(ResultList)

Explanation:

The idea of the code is following this: The matrix Mat[i][j] means the maximum string chain we may get if we can only choose i elements at most and ending element must be words[j]. The commented code is the original code. It has a time complexity of n^3. However, we may improve it, as we may notice that the order of the element in the list should not change the result. Hence we may first sort the string list by the length of the element. Then we may use one dimensional list to store the result .Here ResultList[i] means the maximum number of the string if the ending element is NewWords[i] (Sorted string list). We do not to apply n^2 check scheme as based on the sorted string list, all the possible predecessor given string NewWord[i] are included in the NewWords[k], 0<=k<i-1. Hence we just need to check with n^2 time complexity. The sort scheme (usually) has a complexity of n^2, hence the total time complexity of the code is n^2

Question 120. Triangle

Link:

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

My Code:

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        TriangleLength = len(triangle)
        MinTri = [triangle[0]]
        for i in range(1,TriangleLength):
            CheckLen = len(triangle[i])
            MinList = []
            for j in range(CheckLen):
                if j == 0:
                    MinList.append(triangle[i][0]+MinTri[i-1][0])
                elif j == (CheckLen -1):
                    MinList.append(triangle[i][CheckLen-1]+MinTri[i-1][CheckLen-2])
                else:
                    Min = min(MinTri[i-1][j],MinTri[i-1][j-1])+ triangle[i][j]
                    MinList.append(Min)
            MinTri.append(MinList)
        return min(MinTri[TriangleLength-1])

Explanation: The idea is clear, for each element in the triangle, we search for the minimum path number among all the available previous element, then take the minimum to get the minimum path sum at this point.

Question 322 Coin Change

Link:

https://leetcode.com/problems/coin-change/

My Code:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        else:
            ResultList = [0]
            MinCoin = min(coins)
            for i in range(1,(amount+1)):
                if i < MinCoin:
                    ResultList.append(0)
                else:
                    AvailableCoinList = []
                    for j in range(len(coins)):
                        if coins[j]<=i:
                            AvailableCoinList.append(coins[j])
                    Min = 2**31
                    if i in AvailableCoinList:
                        ResultList.append(1)
                    else:
                        for k in AvailableCoinList:
                            if ResultList[i-k] != 0:
                                Min = min(ResultList[i-k],Min)
                        if Min == 2**31:
                            ResultList.append(0)
                        else:
                            ResultList.append(Min+1)
            if ResultList[amount] == 0:
                return -1
            else:
                return ResultList[amount]

Explanation: The code follows this idea: For an amount n, we check all the coins that is smaller than it, for example k_1,…,k_j as j coins that is available. The DP[i] list is the minimum amount of coins that can achieve amount i with given coin List. so We check all the available coin i in the list, then we take the minimum of all n-i. There are several situations: first, if n is in the coin list, then the answer is 1. Next if n is not in the coin list, then if all the previous n-k_j are zero, then it means we cannot get the number here, hence we return 0. Otherwise we take the minimum of all non- zero n- k_j and then take the minimum and plus 1.

Question 300. Longest Increasing Subsequence

Link

https://leetcode.com/problems/longest-increasing-subsequence/

My Code:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) ==0:
            return 0
        else:
            ResultList = [1]
            for i in range(1,len(nums)):
                Max = 1
                for j in range(i):
                    if nums[i]>nums[j]:
                        Max = max(Max,ResultList[j]+1)
                ResultList.append(Max)
            return max(ResultList)

Explanation: we set the ResultList as the longest subsequence up to element k in the sequence. Then for next element, we just need to check if it is larger than the previous elements. If it is larger, then we just append the element to the previous subsequence, corresponding to the code ResultList[j] +1, then we take the Max among all the possible choices. if it is smaller then all previous elements, then we set the number as 1 in the list.

Then we just need to return the maximum among all the result in the list.

Question 494. Target Sum

Link:

My Code:

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        LargestSum = sum(nums)
        SmallestSum = -LargestSum
        if LargestSum<S or SmallestSum>S:
            return 0
        else:
            ResultMat = []
            for l in range(len(nums)):
                List = [0]*(LargestSum*2+1)
                ResultMat.append(List)
            ResultMat[0][nums[0]] = ResultMat[0][nums[0]]+1
            ResultMat[0][-nums[0]] = ResultMat[0][-nums[0]]+1
            for i in range(1,len(nums)):
                for j in range(-LargestSum,LargestSum+1,1):
                    Index1 = j-nums[i]
                    Index2 = j+nums[i]
                    if Index1 <-LargestSum:
                        Value1 =0
                    else:
                        Value1 = ResultMat[i-1][Index1]
                    if Index2> LargestSum:
                        Value2 = 0
                    else:
                        Value2 = ResultMat[i-1][Index2]
                    Value = Value1+Value2
                    ResultMat[i][j] = Value
            return ResultMat[len(nums)-1][S]

Explanation: I use a two dimension matrix to store the data. The row is the ith element of the original list, the column is the Sum j and the value stored in the matrix[i][j] is the total number that can achieve value j at the ith index. Then to for i+1 Index, the only way to achieve the sum j is that we have achieved j+ nums[i+1] or j-nums[i+1] at the index i. Hence we just sum these two values together to get the total number that can achieve j at i+1.

Question 279. Perfect Squares

Link:

https://leetcode.com/problems/perfect-squares/

My Code:

class Solution:
    def numSquares(self, n: int) -> int:
        if n ==1:
            return 1
        else:
            NumList = [0]
            for Number in range(1,n+1):
                Min = 2**31
                SquareNum = math.floor(math.sqrt(Number))
                for j in range(1,(SquareNum+1)):
                    Min = min(Min,NumList[Number-j**2])
                NumList.append((Min+1))
            return NumList[n]

Explanation

It is clear that we for number a , we may check the number squares the a-k is made of and then take the minimum among them. A typical dynamic programming problem.

1289. Minimum Falling Path Sum II

Link

https://leetcode.com/problems/minimum-falling-path-sum-ii/submissions/

My Code:

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if len(arr) ==1:
            return arr[0][0]
        else:
            Row = len(arr)
            Col = len(arr[0])
            ResultMat = [arr[0]] 
            for i in range(1,Row):
                ResultList = []
                for j in range(Col):
                    NewList= ResultMat[i-1]
                    NewList = NewList[0:j] + NewList[(j+1):len(NewList)]
                    Min = min(NewList)
                    Value = Min+arr[i][j]
                    ResultList.append(Value)
                ResultMat.append(ResultList)
            return min(ResultMat[Row-1])

Explanation: Similar with question 931, just check all the available value and choose the minimum value.