笛卡尔乘积 Cartesian product
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
image.pngExample:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:Although the above answer is in lexicographical order, your answer could be in any order you want.
reletreby's solution，apply itertools
from itertools import product
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if len(digits)==0:
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']}
comb_list = []
for d in digits:
comb_list.append(phone[d])
all_combs = product(*comb_list)
return [''.join(c) for c in all_combs]
official solution:
class Solution:
def __init__(self):
self.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']}
self.output = []
def backtrack(self, combination, next_digits):
if len(next_digits) == 0:
self.output.append(combination)
else:
for letter in self.phone[next_digits[0]]:
self.backtrack(combination + letter, next_digits[1:])
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits:
self.backtrack('', digits)
return self.output
