Selected Writings

DEPRECATED, ref to: ‣

Easy

**Climbing Stairs #70**

class Solution:
    def climbStairs(self, n: int) -> int:
        dp: List[int] = [0] * n
        if n in [1, 2]:
            return n
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]

**Best Time to Buy and Sell Stock #121**

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n: int = len(prices)
        if n == 0:
            return 0
        min_price: int = prices[0]
        # dp: List[int] = [0] * n
        # for i in range(1, n):
        #     min_price = min(min_price, prices[i])
        #     dp[i] = max(dp[i - 1], prices[i] - min_price)
        # return dp[-1]
        dp: int = 0
        for i in range(1, n):
            min_price = min(min_price, prices[i])
            dp = max(dp, prices[i] - min_price)
        return dp

**Maximum Subarray #53**

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        if len(nums) == 1:
            return ans
        
        # dp = copy.deepcopy(nums)
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i - 1])
            ans = max(nums[i], ans)
        return ans

Medium

**Longest Palindromic Substring #5**

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            even_l, even_r = expand(s, i, i)
            odd_l, odd_r = expand(s, i, i + 1)
            if even_r - even_l > odd_r - odd_l:
                l, r = even_l, even_r
            else:
                l, r = odd_l, odd_r
            if r - l > end - start:
                start, end = l, r
        return s[start:end+1]
    

def expand(s: str, left: int, right: int) -> Tuple[int, int]:
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1, right - 1

**Word Break** #139

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n: int = len(s)
        dp: List[bool] = [False] * (n + 1)
        dp[0] = True
        for i in range(n):
            for j in range(i + 1, n + 1):
                if dp[i] and s[i:j] in wordDict:
                    dp[j] = True
        return dp[-1]

**House Robber #198**

class Solution:
    def rob(self, nums: List[int]) -> int:
        n: int = len(nums)
        dp: List[int] = [0] * (n + 1)
        dp[0] = 0
        dp[1] = nums[0]
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2])
        return dp[n]