电话号码的字母组合

Leetcode Link: 17. 电话号码的字母组合 - 力扣（LeetCode）

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

注意本题不会输入 '0' 和 '1'

解法一

思路：本题采用回溯法，只不过本题的回溯起来是有顺序的，譬如说输入的是”234”，那么再遍历的时候，需要先在”2”对应的内容中找，再在”3”对应的内容中找，而不是在”2”剩下的内容中找。

所以每次的 choose 不再是 choose[idx+1:]，而是一个全新的 choose

该题中采用的送入一个idx来表示遍历第几个digits的字母表，有点像好几for循环嵌套的味道，每一层的for表示一个digits，并且按照顺序往里走，然而直接使用for可以发现for循环的层数不是固定的，而是和输入的digits位数有关

题解：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def backtracking(idx):
	        # idx 表示是从第几个 digits 的内容里选东西 
            nonlocal choose
            if len(choose) <= idx:
	            # 注意这里的写法
                res.append("".join(path))
                return 
            
            for c in choose[idx]:
                # 遍历每一个该数字对应的字符
                path.append(c)
                backtracking(idx+1)
                path.pop()
		# 特例，如果没有这个
		# 当输入''的时候，返回的是[""]
        if digits == '':
            return []
 
        lookup = {'2': 'abc', '3':'def', '4':'ghi',
			      '5':'jkl', '6':'mno', '7': 'pqrs',
				  '8':'tuv', '9':'wxyz'}
        choose = []
        for c in digits:
            choose.append(lookup[c])  # choose = List[List[str]]
        
        res = []
        path =[] # List[single str]
        backtracking(0)
        return res
 

复习的时候写的新的 用i来指示当前遍历到哪一个数字了

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        look_up = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", 
                    "8":"tuv", "9":"wxyz"}
        path = []
        res = []
        def bkt(i):
            nonlocal digits, look_up
 
            if i == len(digits):
                res.append("".join(path))
                return
            
            cur_choose = look_up[digits[i]]
 
            for c in cur_choose:
                path.append(c)
                bkt(i+1)
                path.pop()
        
        if digits == "":
            return []
        
        bkt(0)
        return res
 

启发和联系

本题中是不同集合间的组合关系，而组合总和III和组合中的题是同一集合内的组合关系