0017-letter-combinations-of-a-phone-number¶
Try it on leetcode
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 = "2" Output: ["a","b","c"]
Constraints:
1 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Solution(Python)¶
class Solution:
def __init__(self):
self.hashTable = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
self.hashList = [
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
]
def letterCombinations(self, digits: str) -> List[str]:
return self.dfs(digits)
# Time Complexity: O(4^n)
# Space Complexity: O(4^n)
def bfs(self, digits: str) -> List[str]:
n = len(digits)
if n == 0:
return []
res = []
queue = deque([""])
while queue:
s = queue.popleft()
if len(s) == n:
res.append(s)
else:
for letter in self.hashList[int(digits[len(s)])]:
queue.append(s+letter)
return res
# Time Complexity: O(4^n*n)
# Space Complexity: O(n)
def dfs(self, digits: str) -> List[str]:
n = len(digits)
if n == 0:
return []
res = []
def backtrack(candidate,i):
if len(candidate) == n:
res.append("".join(candidate))
return
letters = self.hashTable[digits[i]]
for letter in letters:
candidate.append(letter)
backtrack(candidate,i+1)
candidate.pop()
backtrack([],0)
return res