written at 20/06/02

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
LeetCode 17 - 电话号码的字母组合 - 图1
示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

简单的DFS便可以解决

代码**

  1. class Solution(object):
  3.     def search(self, digits, state):
  4.         if len(digits) == 0:
  5.             self.combination.append(state)
  6.             return
  7.         letters = self.digits_dict[digits[0]]
  8.         digits = digits[1:]
  9.         for letter in letters:
  10.             self.search(digits, state + letter)
  12.     def letterCombinations(self, digits):
  13.         """
  14.         :type digits: str
  15.         :rtype: List[str]
  16.         """
  17.         if len(digits) == 0: # mark
  18.             return []
  19.         self.digits_dict = {
  20.             '2':'abc',
  21.             '3':'def',
  22.             '4':'ghi',
  23.             '5':'jkl',
  24.             '6':'mno',
  25.             '7':'pqrs',
  26.             '8':'tuv',
  27.             '9':'wxyz',
  28.         }
  29.         self.combination = []
  30.         self.search(digits, "")
  31.         return self.combination

**