欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Python数据结构算法--电话号码的字母组合

程序员文章站 2022-04-15 23:21:27
1. 问题Leetcode原题地址给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。示例:2. 思路在本题中,主要就是每个按键可以有不同的选择,在每个节点,也就是按下的数字位置有多个选择,这样就可以先选择一个,之后弹出这个元素,再选择下一个。 def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] num_s...

1. 问题

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
示例:Python数据结构算法--电话号码的字母组合

2. 思路

在本题中,主要就是每个按键可以有不同的选择,在每个节点,也就是按下的数字位置有多个选择,这样就可以先选择一个,之后弹出这个元素,再选择下一个。

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        num_str = {
            '2':'abc',
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'
        }
        res = []
        path = []
        def comb(index):
            if index == len(digits):
                res.append(''.join(path))
                return
            for char in num_str[digits[index]]:
                path.append(char)
                comb(index+1)
                path.pop()
        comb(0)
        return res

3. 总结

回溯问题,总结框架

def permute(nums):
    res = []      # 结果:保存结果路径
    track = []    # 路径:记录在 track 中
    def backtrack(nums, track):
        if  结束条件:
            res.append(track[:])
            return
        for i in 可选择的选项:
            track.append(i)            # 做选择
            backtrack(nums[1:], track)  # 进入下一层决策树
            track.pop()    # 取消选择
    backtrack(nums, track)
    return res

本文地址:https://blog.csdn.net/weixin_42165585/article/details/108237686