23.07.15 Today’s Leetcode

848. Shifting Letters (medium)

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:

        def shift_char(c, num):
            num %= 26
            p = (ord(c) - ord('a') + num) % 26
            return chr(p + ord('a'))

        res = ''
        n = len(s)
        cur = 0
        for i in range(n - 1, -1, -1):
            c = s[i]
            cur += shifts[i]
            res += shift_char(c, cur)
        
        return res[::-1]

1008. Construct Binary Search Tree from Preorder Traversal (medium)

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        
        def dfs(order):
            if not order:
                return None
            print(order)
            node = TreeNode(order[0])
            index = 1
            while index < len(order) and order[index] < order[0]:
                index += 1
            
            node.left = dfs(order[1:index])
            node.right = dfs(order[index:])
            return node
        
        return dfs(preorder)

1751. Maximum Number of Events That Can Be Attended II (hard)

import bisect

class Solution:

    def __init__(self):
        self.events = []

    # Cache decorator to memoize results of function calls
    @cache
    def solve(self, i, k):
        if i >= len(self.events): 
            return 0
        if k <= 0: 
            return 0
        
        # Retrieve start time, end time, and value of current event
        s, e, v = self.events[i]
        
        # Find the next event that starts after the current event ends
        j = bisect.bisect(self.events, [e+1])
        
        # We have two options: either take the current event or don't
        return max(v + self.solve(j, k - 1), self.solve(i + 1, k))

    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort()  # Sort events based on their start times
        self.events = events
        return self.solve(0, k)