23.02.26 Today’s Leetcode
72. Edit Distance (hard)
memoization approach
class Solution:
def minDistance(self, word1, word2):
return self.minDistance2(word1, word2, 0, 0, {})
def minDistance2(self, word1, word2, i, j, memo):
"""Memoized solution"""
if i == len(word1) and j == len(word2):
return 0
if i == len(word1):
return len(word2) - j
if j == len(word2):
return len(word1) - i
if (i, j) not in memo:
if word1[i] == word2[j]:
ans = self.minDistance2(word1, word2, i + 1, j + 1, memo)
else:
insert = 1 + self.minDistance2(word1, word2, i, j + 1, memo)
delete = 1 + self.minDistance2(word1, word2, i + 1, j, memo)
replace = 1 + self.minDistance2(word1, word2, i + 1, j + 1, memo)
ans = min(insert, delete, replace)
memo[(i, j)] = ans
return memo[(i, j)]
DP approach
class Solution:
def minDistance(self, word1, word2):
"""Dynamic programming solution"""
m = len(word1)
n = len(word2)
table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
table[i][0] = i
for j in range(n + 1):
table[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
table[i][j] = table[i - 1][j - 1]
else:
table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])
return table[-1][-1]
148. Sort List (medium)
with Priority Queue (min-heap)
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
arr = []
while head:
heappush(arr, head.val)
head = head.next
res = ListNode(0)
cur = res
while arr:
target = heappop(arr)
cur.val = target
if not arr:
break
cur.next = ListNode(0)
cur = cur.next
return res
150. Evaluate Reverse Polish Notation
Reverse Polish Notation
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
numbers = []
for token in tokens:
if token == '+':
a, b = numbers.pop(), numbers.pop()
numbers.append(b + a)
elif token == '-':
a, b = numbers.pop(), numbers.pop()
numbers.append(b - a)
elif token == '*':
a, b = numbers.pop(), numbers.pop()
numbers.append(b * a)
elif token == '/':
a, b = numbers.pop(), numbers.pop()
numbers.append(int(b / a))
else:
numbers.append(int(token))
# print(numbers)
return numbers[-1]
127. Word Ladder (hard)
BFS Approach. But failed.
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
m = defaultdict(set)
def dis(word1, word2):
n = len(word1)
diff = 0
for i in range(n):
if word1[i] != word2[i]:
diff += 1
return diff
for a in wordList + [beginWord]:
for b in wordList:
if dis(a, b) == 1:
m[a].add(b)
m[b].add(a)
# print(m)
d = {}
queue = [beginWord]
temp = []
dis = 1
while queue:
target = queue.pop(0)
for w in m[target]:
if w not in d:
d[w] = dis
temp.append(w)
if not queue and temp:
queue = temp[:]
temp = []
dis += 1
# print(d)
if endWord in d:
return d[endWord] + 1
return 0
Another solution with BSF Approach. 두 솔루션의 차이점은 next_word를 추출하는 방식이다. 첫번째 솔루션에서 next_word를 추출하는 방식은 두 문자열의 difference가 1인 문자열을 계산하여 dictionary 형태로 저장하고 그 데이터를 사용하는 방식이다. 하지만 두번째 솔루션에서는 임의의 문자열 index를 수정하고 수정된 문자열이 wordList에 속해있는지 체크하는 방식을 사용했다.
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
wordList = set(wordList)
queue = collections.deque([[beginWord, 1]])
while queue:
word, length = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in wordList:
wordList.remove(next_word)
queue.append([next_word, length + 1])
return 0
126. Word Ladder II (hard)
위 문제와 다르게 경로를 추적해야 하므로, DFS 방식으로 접근했다. But Failed. Time complexity 의 문제인것 같은데, 다른 사람들은 BFS를 이용해서 풀었다고도 하니……… BFS로 한번 풀어볼까.
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList = set(wordList)
res = defaultdict(list)
dis = 10**9
n = len(beginWord)
def dfs(cur, history):
nonlocal dis
if cur == endWord:
res[len(history)].append(history[:])
dis = min(dis, len(history))
return
for i in range(n):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = cur[:i] + c + cur[i + 1:]
if next_word in wordList and next_word not in history:
history.append(next_word)
dfs(next_word, history, visited)
history.pop()
dfs(beginWord, [beginWord])
return res[dis]
deque 라는 놈을 어째저째 잘 써먹어야 하나보다. 저번에 한번 봤었던것 같은데… heap 마냥 어떻게 써야하는지 문제를 풀어보면서 감을 잡아야 할 것 같다. 시작점과 끝점에 값을 넣고 빼는것에 대해서 list 보다 월등한 효율을 보여준다고 한다.
class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
def dfs(word):
if word == endWord:
res.append(list(tmp))
return
if word in graph:
for nei in graph[word]:
if dist[nei] == dist[word]-1:
tmp.append(nei)
dfs(nei)
tmp.pop()
wordSet = set(wordList)
if endWord not in wordSet:
return []
alphabets = 'abcdefghijklmnopqrstuvwxyz'
q = collections.deque([(endWord, 0)])
min_dist = float('inf')
seen = set([endWord])
graph = collections.defaultdict(set)
dist = {}
while q:
u, d = q.popleft()
dist[u] = d
for i in range(len(u)):
for alph in alphabets:
new = u[:i]+alph+u[i+1:]
if new == beginWord:
if min_dist > d+1:
min_dist = d+1
graph[beginWord].add(u)
else:
if new in wordSet:
graph[u].add(new)
graph[new].add(u)
if new not in seen:
seen.add(new)
q.append((new, d+1))
if min_dist == float('inf'):
return []
res = []
tmp = [beginWord]
for nei in graph[beginWord]:
if dist[nei] == min_dist-1:
tmp.append(nei)
dfs(nei)
tmp.pop()
return res
116. Populating Next Right Pointers in Each Node (medium)
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
level_node = [[root]]
level = 0
q, temp = [root], []
while q:
target = q.pop(0)
if target.left:
temp.append(target.left)
if target.right:
temp.append(target.right)
if not q and temp:
q = temp[:]
level += 1
level_node.append([])
level_node[level] = temp[:]
temp = []
for nodes in level_node:
n = len(nodes)
for i in range(n - 1):
nodes[i].next = nodes[i + 1]
nodes[-1].next = None
return root
116. Populating Next Right Pointers in Each Node II (medium)
같은 level을 가진 node끼리 next pointer을 설정해주면 되는 문제.
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
level_node = [[root]]
level = 0
q, temp = [root], []
while q:
target = q.pop(0)
if target.left:
temp.append(target.left)
if target.right:
temp.append(target.right)
if not q and temp:
q = temp[:]
level += 1
level_node.append([])
level_node[level] = temp[:]
temp = []
for nodes in level_node:
n = len(nodes)
for i in range(n - 1):
nodes[i].next = nodes[i + 1]
nodes[-1].next = None
return root
2563. Count the Number of Fair Pairs
Sliding window approach : time exceeded at testcase 47/55
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
n = len(nums)
nums.sort()
# print(nums)
i = j = 0
k = n - 1
count = 0
while i < n - 1:
# target = lower - nums[i]
j = i + 1
k = n - 1
while j < n and nums[j] < lower - nums[i]: j += 1
while k > 0 and nums[k] > upper - nums[i]: k -=1
# print(i, j, k)
if k - j + 1 < 0:
break
if i < j and i < k:
count += k - j + 1
i += 1
return count
Binary Search approach
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
return sum([bisect_right(nums, upper - v, i + 1) - bisect_left(nums, lower - v, i + 1) for i,v in enumerate(nums)])