目录

AaronJny

诗酒繁华,书剑天涯。

leetcode第17题 Letter Combinations of a Phone Number(电话号码的字母组合)

比较简单,直接深搜 + 回溯就能够解决的问题。题目的大意是:

给定一个只包含 2-9 的字符串,按照手机按键的映射关系,将它转化为一个只包含 a-z 的字符串,输出这种所有可能的转换字符串。

数字到小写字母的映射关系可以表示如下:

digits_chr_map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }

样例输入:

"23"

样例输出:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

题目链接:https://leetcode.com/problems/letter-combinations-of-a-phone-number/

思路很简单,直接深搜 + 回溯就可以了,所以就不多说了,直接看代码吧,注释比较详细(python3):

class Solution:
    # 存放所有可能的字符串的列表
    combinations = []

    # 数字到字母的映射关系
    digits_chr_map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }

    # 临时存放一种可能字符串的列表
    # 每次深搜+回溯的时候都会修改它
    tmp_chrs = []

    def dfs(self, digits, pos, n):
        """
        当pos<n时,将数字digits[pos]转换成一个符合条件的字母
        :param digits:数字串
        :param pos: 当前处理坐标
        :param n: 数字串的长度
        :return:
        """
        # 当所有数字都被处理完成时
        if pos >= n:
            # 将临时列表中的字母拼接成字符串,保存到结果列表中取
            self.combinations.append(''.join(self.tmp_chrs))
        # 否则
        else:
            num = digits[pos]
            # 获取当前数字对应的字母列表
            chrs = self.digits_chr_map.get(num)
            # 对于每一个可以使用的字母
            for chr in chrs:
                # 尝试选用它
                self.tmp_chrs.append(chr)
                # 然后递归去选择下一个字母
                self.dfs(digits, pos + 1, n)
                # 回溯,撤销选择,以尝试其他选择
                self.tmp_chrs.pop()

    def letterCombinations(self, digits: str):
        # 清空结果集
        self.combinations.clear()
        # 清空临时列表
        self.tmp_chrs.clear()
        # 数字串为空的时候,直接返回空列表
        if len(digits) == 0:
            return []
        # 否则,就计算这个数字串对应的所有可能字符串,并加入到结果集中
        self.dfs(digits, 0, len(digits))
        # 返回结果集的列表形式
        return list(self.combinations)

转载请注明出处:https://blog.csdn.net/aaronjny/article/details/88551005


标题:leetcode第17题 Letter Combinations of a Phone Number(电话号码的字母组合)
作者:AaronJny
地址:https://aaronjny.com/articles/2019/11/06/1573017554442.html