Scribbling

Binary Search 살짝만 바꿔주자 class Solution: def searchInsert(self, nums: List[int], target: int) -> int: return self.binary_search(nums, 0, len(nums)-1, target) def binary_search(self, nums, l, r, target): if l == r: if target

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: from collections import defaultdict dic = defaultdict(list) for s in strs: counter = [0] * 26 for char in s: counter[ord(char) - ord('a')] += 1 dic[tuple(counter)].append(s) return [x for x in dic.values()]

The essence of solving this problem within O(N) time complexity & O(1) memory is using the nums array itself as the hash for its numbers. That is, nums[i] should contain the information about whether i-1 is in nums or not. Here, we should come up with an algorithm that marks nums array without messing up with the original value of nums[i]. Here, I accomplish such an algorithm using negative sign..

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

DFS Solution. from itertools import permutations class Solution: def permute(self, nums: List[int]) -> List[List[int]]: # Using Library # return list(permutations(nums, len(nums))) ret = [] self.helper(nums, [], ret) return ret def helper(self, nums, element, ret): if not nums: ret.append(element) for i, num in enumerate(nums): self.helper(nums[:i]+nums[i+1:], element+[num], ret) A lazy solution..

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() self.ret = [] self.dfs(candidates, target, []) return self.ret def dfs(self, candidates, target, path): if target < 0: return if target == 0: self.ret.append(path) return prev = None for i, candidate in enumerate(candidates): if candidate != prev: prev = candidate self.dfs(candidat..

class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ num_left = 0 for i in range(9): for j in range(9): if board[i][j] == '.': num_left += 1 self.solver(board, num_left) def solver(self, board, num_left): if num_left == 0: return True # Search Blank -> (i, j) start_y, start_x = 0, 0 found_flag = False for t in range..

class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: for i in range(9): for j in range(9): if board[i][j] != '.': # 가로 for k in range(9): if k == j: continue if board[i][j] == board[i][k]: return False # 세로 for k in range(9): if k == i: continue if board[i][j] == board[k][j]: return False # 사각형 start_y = i // 3 * 3 start_x = j // 3 * 3 for y in range(start_y, start_y+3): for ..

생각보다는 쉽게 풀린다. class Solution: def isMatch(self, s: str, p: str) -> bool: n = len(p) m = len(s) # matched[i][j]: (i-1)th pattern matches (j-1)th string matched = [[False] * (m+1) for _ in range(n+1)] matched[0][0] = True for j in range(1, m+1): matched[0][j] = False for i in range(1, n+1): if p[i-1] == '*': matched[i][0] = matched[i-1][0] for i in range(1, n+1): for j in range(1, m+1): if p[i-1] ..

Rotating a matrix 90 degrees clockwise can be achieved just by transposing + mirror reversing. class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ m, n = len(matrix), len(matrix[0]) for i in range(m): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] for i in range(m): for j in range(n//2..