17. Letter Combinations of a Phone Number
- Total Accepted: 104864
- Total Submissions: 335917
- Difficulty: Medium
- Contributors: Admin
Given a digit string, 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.
Input:Digit string "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.
Code
from collections import deque
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits == "": return []
mapping = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
res = deque([''])
for i in digits:
for j in xrange(len(res)):
s = res.popleft()
for k in mapping[int(i)]:
res.append(s + k)
return list(res)
Idea
Use a FIFO queue. Therefore, we can maximally reduce extra space needed.
Reference: https://discuss.leetcode.com/topic/8465/my-java-solution-with-fifo-queue
Code
from collections import deque
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits == "": return []
mapping = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
return reduce(lambda acc, d: [x+y for x in acc for y in mapping[int(d)]], digits, [''])
Idea
Pythonic way using reduce.
Reference: https://discuss.leetcode.com/topic/11783/one-line-python-solution