leecode

leecode20，有效的括号，栈

class Solution:def isValid(self, s: str) -> bool:def check(ch1,ch2):if ch1 == '[' and ch2 == ']':return Trueelif ch1 == '(' and ch2 == ')':return Trueelif ch1 == '{' and ch2 == '}':return Trueelse:return Falsestack = []for i in range(len(s)):if len(stack) == 0 or check(stack[-1],s[i]) == False:stack.append(s[i])elif check(stack[-1],s[i]) == True:stack.pop()if len(stack) == 0:return Trueelse:return False

leecode22，括号生成，dfs+回溯，注意dfs时候的判断条件

class Solution:def generateParenthesis(self, n: int):ans = []path = []def dfs(l,r,path):if r==n:ans.append("".join(path))returnif l<n:path.append('(')dfs(l+1,r,path)path.pop()if l>r:path.append(')')dfs(l,r+1,path)path.pop()return dfs(0,0,[])return ans

leecod17，电话号码的组合，dfs+回溯:停止条件，循环回溯剪枝

class Solution:def letterCombinations(self, digits: str):ans = []res = []hash_map = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}if digits == "":return []def dfs(i,path):if i == len(digits):ans.append("".join(path))returnfor ch in hash_map[int(digits[i])]:path.append(ch)dfs(i+1,path)path.pop()returndfs(0,[])return ans

17，20，22，39