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.
Python Solution 1:
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits: return []
def bt(d, digits, res, cur):
if not digits:
res.append("".join(cur))
return
for c in d[digits[0]]:
cur.append(c)
bt(d, digits[1:], res, cur)
cur.pop()
d = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
res = []
cur = []
bt(d, digits, res, cur)
return res
Python Solution 2:
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits: return []
def recu(digits, s, e):
if s > e:
res.append(''.join(cur))
return
for c in d[digits[s]]:
cur.append(c)
recu(digits, s + 1, e)
cur.pop()
d = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
res = []
cur = []
recu(digits, 0, len(digits) - 1)
return res
Summary:
- permutation and combination are related to backtracking.
近期评论