Documenting LeetCode solving.
Q117
Hard. Graph
BFS
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
nei = collections.defaultdict(list)
wordList.append(beginWord)
# build the adjcent list
for word in wordList:
for i in range(len(word)):
pattern = word[:i] + "*" + word[i + 1:]
nei[pattern].append(word)
# adjcent list:
# {
# *ot: hot, dot, lot
# h*t: hit, hot
# ho*: hot
# *it: hit
# hi*: hit
# do*: dot, dog
# d*t: dot
# d*g: dog
# *og: dog, log, cog
# l*t: lot
# lo*: lot, log
# l*g: log
# c*g: cog
# co*: cog
# }
visit = set([beginWord])
q = deque([beginWord])
res = 1
while q:
for j in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for i in range(len(word)):
pattern = word[:i] + "*" + word[i + 1:]
for neiWord in nei[pattern]:
if neiWord not in visit:
visit.add(neiWord)
q.append(neiWord)
res += 1
return 0
Q118
309. Best Time to Buy and Sell Stock with Cooldown
Medium. 2D DP.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# state: buying or selling?
# if buy -> i + 1
# if sell -> i + 2, cooldown
dp = {} # key: (i, buying), value: max profit
def dfs(i, buying):
if i >= len(prices):
return 0
if (i, buying) in dp:
return dp[(i, buying)]
if buying:
buy = dfs(i + 1, not buying) - prices[i]
cooldown = dfs(i + 1, buying)
dp[(i, buying)] = max(buy, cooldown)
else:
sell = dfs(i + 2, not buying) + prices[i]
cooldown = dfs(i + 1, buying)
dp[(i, buying)] = max(sell, cooldown)
return dp[(i, buying)]
return dfs(0, True)