23.03.24 Today’s Leetcode

1466. Reorder Routes to Make All Paths Lead to the City Zero (medium)

Testcase Failed 73/76

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        connected = [-1] * n
        count = 0
        tree = defaultdict(list)
        for a, b in connections:
            tree[b].append(a)
        
        def dfs(cur, prev):
            if connected[cur] > 0:
                connected[cur] = count
                return
            connected[cur] = count
            for node in tree[cur]:
                if node != prev:
                    dfs(node, cur)
        
        for i in range(n):
            if connected[i] == -1:
                dfs(i, -1)
                count += 1
        
        print(connected)
        return count - 1

New Solution

class Solution:
    def dfs(self, tree, visited, cur):
        change = 0
        visited[cur] = True
        for node in tree[cur]:
            if not visited[abs(node)]:
                change += self.dfs(tree, visited, abs(node)) + (1 if node > 0 else 0)
        return change

    def minReorder(self, n, connections):
        tree = [[] for _ in range(n)]
        for a, b in connections:
            tree[a].append(b)
            tree[b].append(-a)
        visited = [False] * n
        return self.dfs(tree, visited, 0)

345. Reverse Vowels of a String (easy)

class Solution:
    def reverseVowels(self, s: str) -> str:
        split = list(s)
        vowels = [c for c in s if c in 'aeiouAEIOU']
        vowels = vowels[::-1]
        count = 0
        # print(split)
        # print(vowels)
        for index, c in enumerate(split):
            if c in 'aeiouAEIOU':
                split[index] = vowels[count]
                count += 1
        return ''.join(split)

322. Coin Change (medium)

Greedy Approach

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins = sorted(coins, reverse=True)
        print(coins)

        res = 0
        while amount and coins:
            cur = coins.pop(0)
            d = amount // cur
            res += d
            amount -= d * cur
        
        if amount > 0:
            return -1
        return res

DP Approach

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        dp = {}
        def dfs(amount, count):
            if amount in dp:
                return dp[amount]
            if amount < 0:
                return math.inf
            if amount == 0:
                dp[amount] = 0
                return 0
            temp = math.inf
            for coin in coins:
                temp = min(temp, dfs(amount - coin, count + 1) + 1)
            dp[amount] = temp
            return temp

        res = dfs(amount, 0)
        return res if res != math.inf else -1

301. Remove Invalid Parentheses (hard)

Copied Solution

class Solution:
    def removeInvalidParentheses(self, s):
        def dfs(s, l, r, p, sols):
            bal = 0
            for j in range(r, len(s)):
                bal += p.get(s[j], 0)
                if bal < 0:
                    for i in range(l, j + 1):
                        if p.get(s[i], 0) == -1 and (i == l or p.get(s[i - 1], 0) != -1):
                            dfs(s[:i]+s[i + 1:], i, j, p, sols)
                    return
            sols.append(s[::-1])

        cands, sols = [], []
        dfs(s, 0, 0, {"(":1, ")":-1}, cands)
        for cand in cands:
            dfs(cand, 0, 0, {")":1, "(":-1}, sols)
        return sols