動機

複習backtrack

Problem

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = 23Output: [ad,ae,af,bd,be,bf,cd,ce,cf]

Example 2:

Input: digits = Output: []

Example 3:

Input: digits = 2Output: [a,b,c]

 

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Sol

tbl = {}
tbl['2'] = list("abc")
tbl['3'] = list("def")
tbl['4'] = list("ghi")
tbl['5'] = list("jkl")
tbl['6'] = list("mno")
tbl['7'] = list("pqrs")
tbl['8'] = list("tuv")
tbl['9'] = list("wxyz")

class Solution:
    def letterCombinations(self, ds: str) -> List[str]:
        def dfs(i,acc):
            if i == len(ds):
                return [acc]
            else:
                return list(reduce(lambda ret,x: ret+dfs(i+1,acc+x), tbl[ds[i]],[]))
        if ds:
            return dfs(0,"")
        else:
            return []