```python class SnapshotArray: “”” main idea: avoid redundent array copy in other unchanged indexes, use a list to record each snap_id’s value according to each index; use Binary Search to lookup history snap_id and its corresponding value “”” # tc O(N) sc O(N) def init(self, n: int): self.snap_id = 0...
[Read More]
10. Regular Expression Matching
Two round
```python
“””
main idea: evenly distribute parentheses into A, B two groups.
there are different ways to seperate them, one common approach is to use accumutive open parentheses’ odd/even property to mark one group
e.g.
[Read More]
10. Regular Expression Matching
```python class Solution: def isMatch(self, s: str, p: str) -> bool: “"”tc O(SP) sc P(SP) dp[i][j]: s[:i] == p[:j] corner case: if p == “”, its up to if s is empty case 0: s = “” : it’s up to how the p is organized==> axb* will match empty...
[Read More]
417. Pacific Atlantic Water Flow
```python class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: “”” tc O(MN) sc O(MN) M: rows N: cols where is Pacific rigion: [0,x] or [y,0] Atlantic region [xx,n-1] or [m-1,yy] updating res condition: when start from (i,j) can go both pacific and atlantic region main idea: set global state variable...
[Read More]
Lc9
Brute Force:
"""
tc O(lgN) sc O(lgN)
"""
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 :
return False
elif x == 0:
return True
A = []
while x > 0:
A.append(x%10)
x = x//10
return A[::] == A[::-1]
[Read More]