Word Ladder II Minimum Remove to Make Valid Parentheses *Guess the Word *Optimal Account Balancing Reverse String
*Coin Change 2 Reorganize String Move Zeroes *Wildcard Matching Gas Station
Beta
EQ-1
Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note: Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same.
class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]: tree, words, n = collections.defaultdict(set), set(wordList), len(beginWord) if endWord notin wordList: return [] found, bq, eq, nq, rev = False, {beginWord}, {endWord}, set(), False while bq andnot found: words -= set(bq) for xin bq: for y in [x[:i]+c+x[i+1:] for i in range(n) for c in'qwertyuiopasdfghjklzxcvbnm']: if y in words: if y in eq: found = True else: nq.add(y) tree[y].add(x) if rev else tree[x].add(y) bq, nq = nq, set() if len(bq) > len(eq): bq, eq, rev = eq, bq, not rev def bt(x): return [[x]] ifx == endWord else [[x] + rest for y in tree[x] for rest in bt(y)] return bt(beginWord)
while layer: newlayer = collections.defaultdict(list) for w in layer: if w == endWord: res.extend(k for k in layer[w]) else: for i in range(len(w)): for c in'abcdefghijklmnopqrstuvwxyz': neww = w[:i]+c+w[i+1:] if neww in wordList: newlayer[neww]+=[j+[neww] for j in layer[w]]
wordList -= set(newlayer.keys()) layer = newlayer
return res
EQ-2
Given a string s of ‘(‘ , ‘)’ and lowercase English characters. Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
stack, cur = [], '' for c in s: if c == '(': stack += [cur] cur = '' elif c == ')': if stack: cur = stack.pop() + '(' + cur + ')' else: cur += c
while stack: cur = stack.pop() + cur
return cur
EQ-3 *
This problem is an interactive problem new to the LeetCode platform. We are given a word list of unique words, each word is 6 letters long, and one word in this list is chosen as secret. You may call master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters. This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead. For each test case, you have 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or less calls to master.guess and at least one of these guesses was the secret, you pass the testcase. Besides the example test case below, there will be 5 additional test cases, each with 100 words in the word list. The letters of each word in those testcases were chosen independently at random from ‘a’ to ‘z’, such that every word in the given word lists is unique. Example 1: Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]
Explanation: master.guess(“aaaaaa”) returns -1, because “aaaaaa” is not in wordlist. master.guess(“acckzz”) returns 6, because “acckzz” is secret and has all 6 matches. master.guess(“ccbazz”) returns 3, because “ccbazz” has 3 matches. master.guess(“eiowzz”) returns 2, because “eiowzz” has 2 matches. master.guess(“abcczz”) returns 4, because “abcczz” has 4 matches.
We made 5 calls to master.guess and one of them was the secret, so we pass the test case.
# """ # This is Master's API interface. # You should not implement it, or speculate about its implementation # """ # class Master: # def guess(self, word: str) -> int:
defpair_matches(a, b): # count the number of matching characters return sum(c1 == c2 for c1, c2 in zip(a, b))
defmost_overlap_word(): counts = [[0for_in range(26)] for_in range(6)] # counts[i][j] is nb of words with char j at index i for word incandidates: for i, c in enumerate(word): counts[i][ord(c) - ord("a")] += 1
best_score = 0 for word incandidates: score = 0 for i, c in enumerate(word): score += counts[i][ord(c) - ord("a")] # all words with same chars in same positions if score > best_score: best_score = score best_word = word
return best_word
candidates = wordlist[:] # all remaining candidates, initially all words whilecandidates:
s = most_overlap_word() # guess the word that overlaps with most others matches = master.guess(s)
if matches == 6: return
candidates = [w for w in candidates if pair_matches(s, w) == matches] # filter words with same matches
EQ-4 *
A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill’s lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person’s ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]]. Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note: A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0. Person’s IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Input: [[0,1,10], [2,0,5]] Output: 2
Explanation: Person #0 gave person #1 $10. Person #2 gave person #0 $5. Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.`
Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters.
1 2 3 4 5 6 7 8 9 10 11 12
# 344. Reverse String
classSolution: defreverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ left, right = 0, len(s) - 1 while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1
EQ-6 *
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
for coin in coins: forx in range(coin, amount + 1): dp[x] += dp[x - coin] returndp[amount]
EQ-7
Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same. If possible, output any possible result. If not possible, return the empty string.
# 767. Reorganize String classSolution: def reorganizeString(self, S: str) -> str: N = len(S) A = [] for c, x in sorted((S.count(x), x) for x in set(S)): if c > (N+1)//2: return "" A.extend(c * x) ans = [None] * N ans[::2], ans[1::2] = A[N//2:], A[:N//2] return "".join(ans)
pq = [(-S.count(x), x) for x in set(S)] heapq.heapify(pq) if any(-nc > (len(S) + 1) / 2 for nc, x in pq): return ""
ans = [] while len(pq) >= 2: nct1, ch1 = heapq.heappop(pq) nct2, ch2 = heapq.heappop(pq) #This code turns out to be superfluous, but explains what is happening #if not ans or ch1 != ans[-1]: # ans.extend([ch1, ch2]) #else: # ans.extend([ch2, ch1]) ans.extend([ch1, ch2]) if nct1 + 1: heapq.heappush(pq, (nct1 + 1, ch1)) if nct2 + 1: heapq.heappush(pq, (nct2 + 1, ch2))
return "".join(ans) + (pq[0][1] ifpqelse '')
EQ-8
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements. Input: [0,1,0,3,12] Output: [1,3,12,0,0]
classSolution: defmoveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ idx = 0 for i in range(len(nums)): if nums[i] != 0: nums[idx] = nums[i] idx += 1 while idx < len(nums): nums[idx] = 0 idx += 1 return nums
classSolution1: defmoveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ i = 0 b = [] while i < len(nums): if nums[i] == 0: del(nums[i]) b.append(0) else: i += 1 nums += b
EQ-9 *
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*‘. The matching should cover the entire input string (not partial).
‘?’ Matches any single character.
‘*‘ Matches any sequence of characters (including the empty sequence).
Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ? or *.
# s 走完，p 还有剩下的 * while j < n and p[j] == '*': j += 1
return j == n
EQ-10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# 134. Gas Station
class Solution: defcanCompleteCircuit(self,gas:List[int],cost:List[int])->int: n=len(gas) total_tank,curr_tank=0,0 starting_station=0
foriinrange(n): total_tank+=gas[i]-cost[i] curr_tank+=gas[i]-cost[i] # If one couldn't get here, ifcurr_tank<0: # Pick up the next station as the starting one. starting_station=i+1 # Start with an empty tank. curr_tank=0