241. Different Ways to Add Parentheses （Medium）
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
if '+' not in expression and '-' not in expression and '*' not in expression: return [int(expression)]
res = []
for i in range(len(expression)):
if expression[i] in '+-*':
op = expression[i]
head = expression[:i]
tail = expression[i+1:]
for l in self.diffWaysToCompute(head):
for r in self.diffWaysToCompute(tail):
if op=='+':
res.append(l+r)
if op=='-':
res.append(l-r)
if op=='*':
res.append(l*r)
return res
感觉是backtracking但写code出现了问题。。。并不是 a+(b+...) 和 (a+b)+.... 这2种情况， 而是 （left）+ （right）产生不同的组合。
242. Valid Anagram （Easy）
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return collections.Counter(s)==collections.Counter(t)
答案用了26个字符的数组存储出现次数，s出现+1，t出现-1. 这样相等时候所有位置都应该是0.
243. Shortest Word Distance (Easy)
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
visited = dict()
res=float('inf')
for i,w in enumerate(wordsDict):
if w==word1 and word2 in visited:
res=min(res,i-visited[word2])
if w==word2 and word1 in visited:
res=min(res,i-visited[word1])
visited[w]=i
return res
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
dic = dict()
res = len(wordsDict)
for i,w in enumerate(wordsDict):
dic[w] = i
if word1 in dic and word2 in dic:
res = min(res,abs(dic[word1]-dic[word2]))
return res
244. Shortest Word Distance II (Medium)
class WordDistance:
def __init__(self, wordsDict: List[str]):
self.dic = collections.defaultdict(list)
for i,w in enumerate(wordsDict):
self.dic[w].append(i)
def shortest(self, word1: str, word2: str) -> int:
res=float('inf')
for pos1 in self.dic[word1]:
for pos2 in self.dic[word2]:
res=min(res,abs(pos2-pos1))
return res
245. Shortest Word Distance III (Medium)
class Solution:
def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
dic=dict()
res = float('inf')
for i, w in enumerate(wordsDict):
if w==word1 and word2 in dic:
res=min(res,i-dic[word2])
if w==word2 and word1 in dic:
res=min(res,i-dic[word1])
dic[w]=i
return res
246. Strobogrammatic Number (Easy)
class Solution:
def isStrobogrammatic(self, num: str) -> bool:
l=0
r=len(num)-1
while l<=r:
if l==r:
if num[l] not in {'8','1','0'}:
return False
return True
if num[l]=='6':
if num[r]!='9':
return False
elif num[l]=='9':
if num[r]!='6':
return False
elif num[l]=='8':
if num[r]!='8':
return False
elif num[l]=='1':
if num[r]!='1':
return False
elif num[l]=='0':
if num[r]!='0':
return False
else:
return False
l+=1
r-=1
return True
class Solution:
def isStrobogrammatic(self, num: str) -> bool:
# 1 6 9 8 0
if '2' in num or '3' in num or '4' in num or '5' in num or '7' in num:
return False
dic={'6':'9','9':'6','1':'1','8':'8','0':'0'}
num2= ''.join([dic[e] for e in num][::-1])
return num==num2
247. Strobogrammatic Number II (Medium)
#MY ANSWER
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
if n==1:
return ["0","1","8"]
elif n==2:
return ["11","69","88","96"]
odd = ["0","1","8"]
even = ['00', "11","69","88","96"]
res = []
if n%2==1:
#odd case
for o in odd:
for num in self.findStrobogrammatic(n-1):
l=len(num)
res.append( num[:l//2]+o+num[l//2:])
else:
for e in even:
for num in self.findStrobogrammatic(n-2):
l=len(num)
res.append( num[:l//2]+e+num[l//2:])
return res
#MY ANSWER
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
mid = ['1','8','0']
wing = ['6','9']
dic = {'6':'9','9':'6','8':'8','0':'0','1':'1'}
if n==1: return mid
res = []
def build_head(n):
res = []
def helper(n,tmp):
if n==0:
res.append(tmp)
return
else:
for i in '18069':
tmp+=i
helper(n-1,tmp)
tmp=tmp[:-1]
helper(n,'')
return [e for e in res if e[0]!='0']
if n%2==1:
tmp = build_head((n-1)//2)
for e in tmp:
for m in mid:
res.append(e+m+''.join([dic[ee] for ee in e][::-1]))
else:
tmp = build_head(n//2)
for e in tmp:
res.append(e+''.join([dic[ee] for ee in e][::-1]))
return res
答案思路：
n == 1: [0, 1, 8]
n == 2: [11, 88, 69, 96]
How about n == 3?
=> it can be retrieved if you insert [0, 1, 8] to the middle of solution of n == 2
n == 4?
=> it can be retrieved if you insert [11, 88, 69, 96, 00] to the middle of solution of n == 2
n == 5?
=> it can be retrieved if you insert [0, 1, 8] to the middle of solution of n == 4
the same, for n == 6, it can be retrieved if you insert [11, 88, 69, 96, 00] to the middle of solution of n == 4
248. Strobogrammatic Number III （Hard）
class Solution:
def strobogrammaticInRange(self, low: str, high: str) -> int:
dic = {'0': '0','1': '1','6': '9','8': '8','9': '6'}
count = 0
def dfs(tmp, left,right):
nonlocal count
if left>right:
s=''.join(tmp)
if (len(s)==len(low) and s<low) or (len(s)==len(high) and s>high):
return
count+=1
return
for k,v in dic.items():
tmp[left] = k
tmp[right] = v
if len(tmp)!=1 and tmp[0]=='0':
continue
if left==right and k!=v:
continue
dfs(tmp,left+1,right-1)
for length in range(len(low),len(high)+1):
dfs(['']*length,0,length-1)
return count
give up, 思路 ， 构建length长度的满足条件的string，从两边向中间构建。 做dfs search。
249. Group Shifted Strings （Medium）
We can shift a string by shifting each of its letters to its successive letter.
For example, "abc" can be shifted to be "bcd".
We can keep shifting the string to form a sequence.
For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".
Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
dic = collections.defaultdict(list)
for s in strings:
if len(s)==1:
dic['NULL'].append(s)
else:
key=[]
for i in range(1,len(s)):
tmp = str((ord(s[i])-ord(s[i-1]))%26)
key.append(tmp)
key='-'.join(key)
dic[key].append(s)
return dic.values()
250. Count Univalue Subtrees (Medium)
Given the root of a binary tree, return the number of uni-value subtrees.
A uni-value subtree means all nodes of the subtree have the same value.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
count = [0]
def isUnivalSubtrees(root):
if not root:
return False
if not root.left and not root.right:
count[0]+=1
return True
if not root.left:
res = isUnivalSubtrees(root.right) and root.val==root.right.val
if res:
count[0]+=1
return res
if not root.right:
res= isUnivalSubtrees(root.left) and root.val==root.left.val
if res:
count[0]+=1
return res
left = isUnivalSubtrees(root.left)
right= isUnivalSubtrees(root.right)
res=left and right and root.val==root.left.val and root.val==root.right.val
if res:
count[0]+=1
return res
isUnivalSubtrees(root)
return count[0]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
# bottom up
# post order
res = 0
def isU(node):
nonlocal res
if not node:
return True
if not node.left and not node.right:
res+=1
return True
if not node.left:
r = isU(node.right) and node.val==node.right.val
if r:
res+=1
return r
if not root.right:
r = isU(node.left) and node.val==node.left.val
if r:
res+=1
return r
left = isU(node.left)
right = isU(node.right)
r = left and right and node.val==node.left.val and node.val==node.right.val
if r:
res+=1
return r
isU(root)
return res