Scribbling

class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n+1) dp[0] = 1 dp[1] = 1 for i in range(2, n+1): count = 0 for j in range(1, i+1): count += dp[j-1] * dp[i-j] dp[i] = count return dp[n]

# 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 generateTrees(self, n: int) -> List[Optional[TreeNode]]: return self.tree_maker([i for i in range(1, n+1)]) def tree_maker(self, nums): if not nums: return [None] ret = [] for i, num in enumerate(nums): lefts = sel..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: new_head = ListNode(val=0, next=head) count = 0 ptr = new_head prev, cur = None, new_head nxt = head for i in range(left): prev = cur cur = nxt nxt = cur...

DFS version class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: if len(s1) + len(s2) != len(s3): return False self.s1 = s1 self.s2 = s2 self.s3 = s3 self.dp = set() return self.dfs(0, 0, 0) def dfs(self, i, j, k): if (i, j, k) in self.dp: return False if k == len(self.s3): return True if i < len(self.s1) and self.s1[i] == self.s3[k]: if self.dfs(i+1, j, k+1): return True i..

class Solution: def restoreIpAddresses(self, s: str) -> List[str]: self.ret = [] self.nums = set([str(i) for i in range(256)]) self.helper(s, []) return self.ret def helper(self, s, ip): if len(ip) == 4: if not s: self.ret.append('.'.join(ip)) return if not s: return for i in range(min(3, len(s))): if s[:i+1] in self.nums: self.helper(s[i+1:], ip+[s[:i+1]])

class Solution: def numDecodings(self, s: str) -> int: candidates = set([str(i) for i in range(1, 27)]) # dp[i] denotes # of ways until s[i-1] dp = [0] * (len(s) + 1) dp[0] = 1 if s[0] in candidates: dp[1] = 1 for i in range(2, len(s)+1): # dp[n] = dp[n-2] * k2 + dp[n-1] * k1 k2 = 0 if s[i-2:i] in candidates: k2 += 1 k1 = 0 if s[i-1] in candidates: k1 += 1 dp[i] = dp[i-2] * k2 + dp[i-1] * k1 ret..

BFS로 순회해보자 # 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 from collections import deque class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if p == None and q == None: return True if p == None and q != None: return False if p != None and q =..

class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() self.ret = [] self.dfs(nums, []) return self.ret def dfs(self, nums, path): self.ret.append(path) prev = None for i, num in enumerate(nums): if num != prev: prev = num self.dfs(nums[i+1:], path+[num]) Lazy version: class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() sel..

The key here is that we need to push elements from nums2 to nums1 while not disturbing the existing elements in nums1. So, put the elems from nums2 to nums1 from the end. class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ p1, p2 = m - 1, n - 1 for i in range(m+n-1, -1, -1): p1_val = nums1[p1]..

Binary Search Tree의 Validation 문제이다. BST 특성상 아래와 같이 순회하면 정렬된다는 특성을 이용한다. 즉, 순회하면서 점점 value가 커지는지만 체크하면 끝. # 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 isValidBST(self, root: Optional[TreeNode]) -> bool: self.reg = -pow(2, 31) - 1 return self.dfs(root) def dfs..