- 17 Letter Combinations of a Phone Number
- 难度：Medium｜ 中等
- 相关知识点：Hash Table| String |Backtracking
- 题目链接：https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
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 digits 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'].
Solution 1:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
phone = {'2':['a','b','c'],
'3':['d','e','f'],
'4':['g','h','i'],
'5':['j','k','l'],
'6':['m','n','o'],
'7':['p','q','r','s'],
'8':['t','u','v'],
'9':['w','x','y','z']}
def backtrack(conbination,nextdigit):
if len(nextdigit) == 0:
res.append(conbination)
else:
for letter in phone[nextdigit[0]]:
backtrack(conbination + letter,nextdigit[1:])
res = []
backtrack('',digits)
return res- 时间复杂度: O(3^m * 4^n)，其中 m 是对应四个字母的数字个数，n 是对应三个字母的数字个数
- 空间复杂度: O(3^m * 4^n)
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
phone = {'2':['a','b','c'],
'3':['d','e','f'],
'4':['g','h','i'],
'5':['j','k','l'],
'6':['m','n','o'],
'7':['p','q','r','s'],
'8':['t','u','v'],
'9':['w','x','y','z']}
ans = ['']
if not digits: return []
for digit in digits:
for i in range(len(ans)):
s = ans.pop(0)
for i in phone[digit]:
ans.append(s+i)
return ans