leetcode-016

Alpha

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 126. Word Ladder II

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 not in wordList: return []
found, bq, eq, nq, rev = False, {beginWord}, {endWord}, set(), False
while bq and not found:
words -= set(bq)
for x in 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]] if x == endWord else [[x] + rest for y in tree[x] for rest in bt(y)]
return bt(beginWord)


class Solution1:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList = set(wordList)
res = []
layer = {}
layer[beginWord] = [[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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 1249. Minimum Remove to Make Valid Parentheses

class Solution:
def minRemoveToMakeValid(self, s: str) -> str:

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 843. Guess the Word

# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master:
# def guess(self, word: str) -> int:

class Solution(object):
def findSecretWord(self, wordlist, master):

def pair_matches(a, b): # count the number of matching characters
return sum(c1 == c2 for c1, c2 in zip(a, b))

def most_overlap_word():
counts = [[0 for _ in range(26)] for _ in range(6)] # counts[i][j] is nb of words with char j at index i
for word in candidates:
for i, c in enumerate(word):
counts[i][ord(c) - ord("a")] += 1

best_score = 0
for word in candidates:
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
while candidates:

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.`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 465. Optimal Account Balancing

class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
def remove_one_zero_clique(non_zero):
n = len(non_zero)
q = collections.deque()
# q store ([index set], sum of set)
q.append(([0], non_zero[0]))
min_zero_set = None

while q:
cur_set, cur_sum = q.popleft()
if cur_sum == 0:
min_zero_set = cur_set
break
for j in range(cur_set[-1] + 1, n):
q.append((cur_set + [j], cur_sum + non_zero[j]))

min_zero_set = set(min_zero_set)
return [non_zero[i] for i in range(n) if i not in min_zero_set]


bal = collections.defaultdict(int)
for t in transactions:
bal[t[0]] -= t[2]
bal[t[1]] += t[2]
non_zero = [bal[k] for k in bal if bal[k] != 0]

bal_cnt = len(non_zero)
while len(non_zero) > 0:
non_zero = remove_one_zero_clique(non_zero)
bal_cnt -= 1
return bal_cnt

EQ-5

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

class Solution:
def reverseString(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

1
2
3
4
5
6
7
8
9
10
11
# 518. Coin Change 2

class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1

for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
return dp[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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 767. Reorganize String

class Solution:
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)


class Solution1:
def reorganizeString(self, S: str) -> str:

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] if pq else '')

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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 283. Move Zeroes

class Solution:
def moveZeroes(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


class Solution1:
def moveZeroes(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 *.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 44. Wildcard Matching

class Solution:
def isMatch(self, s: str, p: str) -> bool:

m, n = len(s), len(p)
i, j = 0, 0
i_start = -1
j_start = -1

# 用 p 把 s 匹配完,所以出循环式,保证 i 走完原串
while i < m:

# 恰好匹配char-char
if j < n and (s[i] == p[j] or p[j] == '?'):
i += 1
j += 1

# 出现 * 号,更新比对 i,j
elif j < n and p[j] == '*':
j_start = j + 1
i_start = i
i, j = i_start, j_start

# 之前出现过 * 号,现在匹配不上,重置起始对比位置
# i_start 起始位多一个,j_start 不变;意思是 p 里的 * 匹配了一个 s 的字母
elif i_start != -1 and j_start != -1:
i_start += 1
i, j = i_start, j_start

else:

return False

# 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:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
total_tank, curr_tank = 0, 0
starting_station = 0

for i in range(n):
total_tank += gas[i] - cost[i]
curr_tank += gas[i] - cost[i]
# If one couldn't get here,
if curr_tank < 0:
# Pick up the next station as the starting one.
starting_station = i + 1
# Start with an empty tank.
curr_tank = 0

return starting_station if total_tank >= 0 else -1

Sigma

Feb 13, 2020
La Jolla, CA

Omega

https://leetcode.com/