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