LeetCode高频算法面试题 - 017 - 电话号码的字母组合

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

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

题目难度: ★★★, 中等

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

解题思路

• 使用递归， 从左往右遍历digits字符串(假如: "23")
• 当遍历第k位置字符串, 依次取出digits[k]的对应的 字符串alpha，假如digits[k]=2, 那么对应的组合"abc"
• 依次遍历alpha字符串(这里是 "abc"), 取出每一个字符(第一个是a), 导入到str字符串末尾
  • 然后深度递归遍历 下一个digists 字符串, k+1
  • 一直深度遍历直到 k = n, 表明遍历到末尾了， 这时str里面保留的digists 对应的一条完整链路的字符串
• 剔除刚才放到str里面的最后一个字符(a), for循环继续深度遍历下一个b字符， 再次深度遍历; 然后是c...

代码实现

tips: 以下代码是使用Go代码实现的不同解法, 文章最后可以看C++、C、Java、Python实现

var result []string
var m = map[byte]string{
  '2': "abc",
  '3': "def",
  '4': "ghi",
  '5': "jkl",
  '6': "mno",
  '7': "pqrs",
  '8': "tuv",
  '9': "wxyz",
}

func run(digits string, str []byte, k, n int) {
  if k == n {
    if len(str) > 0 {
      result = append(result, string(str))
    }
    return
  }
  alpha := m[digits[k]]
  for i := 0; i < len(alpha); i++ {
    str = append(str, alpha[i])
    run(digits, str, k+1, n)
    str = str[:len(str)-1] // 剔除str最后一个字符 alpha[i]
  }
}

func letterCombinations(digits string) []string {
  result = []string{}
  run(digits, []byte{}, 0, len(digits))
  return result
}

其他语言版本

1、Python3

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        phone = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
        queue = ['']  # 初始化队列
        for digit in digits:
            for _ in range(len(queue)):
                tmp = queue.pop(0)
                for letter in phone[ord(digit)-50]:# 这里我们不使用 int() 转换字符串，使用ASCII码
                    queue.append(tmp + letter)
        return queue

也欢迎关注我的公众号: 漫步coding。 一起交流, 在coding的世界里漫步。