- Letter Combinations of a Phone Number
中等
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
LeetCode 相关企业
- 亚马逊 Amazon|35
- 微软 Microsoft|23
- Facebook|12
- 优步 Uber|9
- 苹果 Apple|8
- 谷歌 Google|6
- 字节跳动|5
- 彭博 Bloomberg|5
- 甲骨文 Oracle|2
相关标签
- Hash Table
- String
- Backtracking
相似题目
- Generate Parentheses 中等
- Combination Sum 中等
- Binary Watch 简单
# const.py
KEYBOARDS = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
digitsLeng = len(digits)
if digitsLeng == 0:
return []
results = []
self.dfs(digits, digitsLeng, 0, [], results)
return results
def dfs(self, digits, digitsLeng, currIndex, currSubset, results):
if currIndex == digitsLeng:
results.append("".join(currSubset))
return
for currletter in KEYBOARDS[digits[currIndex]]:
currSubset.append(currletter)
self.dfs(digits, digitsLeng, currIndex + 1, currSubset, results)
currSubset.pop() #cannot use remove() bc it may delete repeated letter