组合
2020-03-08 本文已影响0人
madao756
0X00 模板题目
class Solution:
def __init__(self):
self.num_letter = {
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz",
}
def letterCombinations(self, digits: str) -> List[str]:
ans = []
if len(digits) == 0:
return ans
cur = ['' for _ in range(len(digits))]
def dfs(idx):
if len(digits) == idx:
ans.append(''.join(cur))
return
n = digits[idx]
for c in self.num_letter[n]:
cur[idx] = c
dfs(idx + 1)
dfs(0)
return ans
class Solution:
def expand(self, S: str) -> List[str]:
# 组合题
# 生成所有的组合
if S == 0: return None
options = []
inBrace = False
temp = []
for c in S:
if inBrace and c.isalpha():
temp.append(c)
elif c.isalpha():
temp.append(c)
elif c == "{":
inBrace = True
if not temp: continue
options.append(["".join(temp)])
temp = []
elif c == "}":
inBrace = False
temp.sort()
options.append(temp)
temp = []
if temp: options.append(["".join(temp)])
cur = [''] * len(options)
ans = []
def dfs(idx):
if idx == len(options):
ans.append("".join(cur))
return
for i in options[idx]:
cur[idx] = i
dfs(idx+1)
dfs(0)
return ans
0X01 注意事项
什么时候使用「组合」
遇到多个集合之间,元素互相组合的时候使用组合, 比如我上面的两道例题
