Letter Combinations of a Phone Number

题目描述

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"].

解题方法

这个题目也是DFS的题，因为这里的电话号码是有顺序的，所以是subsets的问题

• 用一个array记录可以替换的characters
• 然后的code就与subsets的模板基本一样了

Solution

class Solution(object):
    def __init__(self):
        self.dtcMap = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []

        results = []
        self.helper(results, digits, 0, [])

        return results

    def helper(self, results, digits, index, curList):
        if len(curList) == len(digits):
            newStr = "".join(curList)
            results.append(newStr)

        for i in range(index, len(digits)):
            cOptions = self.dtcMap[int(digits[i])]
            for j in range(len(cOptions)):
                curList.append(cOptions[j])
                self.helper(results, digits, i+1, curList)
                curList.pop()

Reference