1. Decode Ways

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)

        # Base case
        if n > 0 and s[0] == '0':
            return 0

        # Init n + 1 items
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1

        for i in range(2, n + 1):
            one_digit = s[i - 1]
            two_digit = s[i - 2:i]

            if 1 <= int(one_digit) <= 9:
                dp[i] += dp[i - 1]
            if 10 <= int(two_digit) <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

2. 2D Prefix Matrix

3. Rotate Matrix

• Run from the bottom of the column to row

• Continue in another column

4. Min Cost Climbing Stairs

• DP theo cost(i - 1), and cost(i - 2) + cost[i]

• Top down: cost[i] + min(dfs(i + 1), dfs(i + 2))

• Backward: for i in range(len(cost) - 3, -1, -1) => cost[i] += min(cost[i + 1], cost[i + 2])

• Bottom-up: dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

5. Sort an Array

• Heap Sort

• Merge Sort

• Quick Sort

6. Word Ladder

• Idea: BFS.

• Time Complexity: O(N^2 x M (list))

7. Delete Node in a BST

8. Minimum Interval to Include Each Query

• Sort by length interval.

9. Partition Labels

10. Combination Sum 2

11. Climb Stairs

12. Design Twitter