Documenting LeetCode solving.
Q1
Medium. Array
The trick here is when dealing with the squares, we bundle each 3 rows and columns together and use (row/3, column/3) to find which block the item belongs to.
From Neetcode, youtube.com/watch?v=TjFXEUCMqI8
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# Use defaultdict instead of {} to initualize the dictionary
# because defaultdict is able to provide a default value
# for a key that does not exist.
rows = collections.defaultdict(set)
cols = collections.defaultdict(set)
squares = collections.defaultdict(set) # key = (r // 3, c // 3)
for r in range(9):
for c in range(9):
if board[r][c] == '.':
continue
if (board[r][c] in rows[r] or
board[r][c] in cols[c] or
board[r][c] in squares[(r // 3, c // 3)]):
return False
rows[r].add(board[r][c])
cols[c].add(board[r][c])
squares[(r // 3, c // 3)].add(board[r][c])
return True
Q2
271. Encode and Decode Strings
Medium. String
Use the length of each string and a "#" key to separate each string.
For example:
Encode: ["leet", "code"] -> "4#leet4#code".
class Codec:
def encode(self, strs: List[str]) -> str:
"""Encodes a list of strings to a single string.
"""
res = ""
for s in strs:
res += str(len(s)) + "#" + s
return res
def decode(self, s: str) -> List[str]:
"""Decodes a single string to a list of strings.
"""
res = []
i = 0
while i < len(s):
j = i
while s[j] != "#":
j += 1
length = int(s[i : j])
res.append(s[j + 1 : j + 1 + length])
i = j + 1 + length
return res
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))
Q3
128. Longest Consecutive Sequence
Medium. Array
The trick here is to find the beginning of a sequence, which doesn't have the left number. So we check every number to see if it has the left number or not.
From Neetcode, youtube.com/watch?v=P6RZZMu_maU
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numsSet = set(nums)
longest = 0
for n in nums:
if (n - 1) not in numsSet:
length = 0
while (n + length) in numsSet:
length += 1
longest = max(longest, length)
return longest