My website

top down DP ```python time O(N) space O(N) class Solution: def knightDialer(self, n: int) -> int: dp = [[[0]*3 for _ in range(4)] for _ in range(n+1)] self.m = 10**9+7 self.dir = [(-1,-2),(-1,2),(1,-2),(1,2),(-2,-1),(-2,1),(2,-1),(2,1)] res = 0 for i in range(4): for j in range(3): res = (res + self.dfs(dp,i,j,n)) %... [Read More]

```python main idea: DFS create set to record all rooms can be open dfs recursively traverse non-visited rooms within current room’s keys at lowest level, check if len visited rooms == len all rooms class Solution: def canVisitAllRooms(self, rooms: List[List[int]]) -> bool: # time O(N+K) space O(N) seen = set()... [Read More]

class Solution: def backspaceCompare(self, S: str, T: str) -> bool: """tc O(N+M) sc O(N+M) : N: length of S, M: length of T main idea: two ptr get each string's final revised string, compare 1. right ptr keep loop to the end 2. if s[r] != #, left ptr forward... [Read More]

main idea: 0. be aware of edge case r == 0, c == 0 1. for each row, caculate accumulative height, 2 . use algorithm from LC75(caculate histogram max area) to caculte max area ```python class Solution: time O(R*C) space O(C) def maximalRectangle(self, matrix: List[List[str]]) -> int: if not matrix:... [Read More]

Optimal solution ```python Definition for a binary tree node. class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: “”” tc O(N) sc O(N) """ # mapping val and idx of inorder d =... [Read More]