一周编程集训day6：实战递归

1 任务

实战递归：完成Leetcode上的Letter Combinations of a Phone Number(17)及permutations(46)！ 同时温习前五天内容，做出总结！

2 leetcode

1.17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

python解答思路：

• 用dict表示号码字母对应关系
• 利用递归对输入数字对应的字母进行逐个遍历，利用列表对字母的组合进行拼接。

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        res = []  # 保存数字对应的字母组合结果
        dic = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}  # 数字对应字母保存为字典
        if len(digits) == 0:
            return []
        
        for i in dic[digits[0]]:  # 遍历第一个数字对应的字母
            if len(digits) == 1:  # 输入只有一个数字
                res.append(i)
                if i == dic[digits[0]][-1]: # 遍历到最后一个数字
                    return res
            else:
                for j in self.letterCombinations(digits[1:]):
                    res.append(i + j)
                    if i == dic[digits[0]][-1] and j == self.letterCombinations(digits[1:])[-1]:  # 遍历到最后一个
                        return res

leetcode提交结果：

2.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

python解答思路：n个数的全排列，就是n的阶乘，为nn-1…*1，迭代每个位置的可能性。

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        length = len(nums)
        
        if length == 1 or length == 0:
            return [nums]
        
        res = []
        
        for i in range(length):
            list_one = self.permute(nums[0:i]+(nums[i+1:])) # 迭代要去除已有数据nums更新为nums[0: i]
            for j in list_one:
                res.append([nums[i]] + j)
        return res

leetcode提交结果：

3 参考

1. 代码参考