TagDp

# 5. Longest Palindromic Substring

# string s, find the longest palindromic substring in s.

class Solution:

    def longestPalindrome(self, s: str) -> str:

        res = ""

        for i in range(len(s)):

            # odd case, like "aba"

            tmp = self.helper(s, i, i)

            if len(tmp) > len(res):

                res = tmp

            # even case, like "abba"

            tmp = self.helper(s, i, i+1)

            if len(tmp) > len(res):

                res = tmp

        return res

    # get the longest palindrome, l, r are the middle indexes 

    # from inner to outer

    def helper(self, s, l, r):

        while l >= 0 and r < len(s) and s[l] == s[r]:

            l -= 1; r += 1

        return s[l+1:r]

# Maximum Subarray
# In: Array
#=>contiguous subarray ; Largest Sum

class Solution:
    def maxSubArray(self, A: List[int]) -> int:
        if not A:
            return 0
        curSum = maxSum = A[0]
        for num in A[1:]:                    #遍历一遍 同时寻找当前局部最大和 与历史最大和
            curSum = max(num, curSum + num)  #当前值 加入 或开始
            maxSum = max(maxSum, curSum)     #当前处的最大和
        return maxSum

# 121. Best Time to Buy and Sell Stock
# In:  ith element => price day i.
# one transaction (buy one and sell one)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:      
        if not prices:
            return 0
        loc = glo = 0
        for i in range(1, len(prices)):
            loc = max(loc+prices[i]-prices[i-1], 0)
            glo = max(glo, loc)
        return glo

# Coin Change
# In: coins[]; amount;
# Out: fewest number;

# Assume dp[i] is the fewest number of coins making up amount i, 
# then for every coin in coins, dp[i] = min(dp[i - coin] + 1).
# The time complexity is O(amount * coins.length) and the space complexity is O(amount)
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
        dp = [0] + [float('inf') for i in range(amount)]
        for i in range(1, amount+1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        if dp[-1] == float('inf'):
            return -1
        return dp[-1]

# Word Break
# non-empty string s 
# wordDict: list of non-empty words, 
# s can be segmented; one or more dictionary words?
# class Solution:
#     def wordBreak(self, s, words):
#         ok = [True]
#         for i in range(1, len(s)+1):
#             ok += any(ok[j] and s[j:i] in words for j in range(i)),
#         return ok[-1]
    
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True] + [False] * len(s)
        for i in range(1, len(s) + 1):
            for word in wordDict:
                if s[:i].endswith(word):
                    dp[i] |= dp[i-len(word)]
        return dp[-1]