Letter Combination

题目描述

Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解题方法

DFS/Backtracking的方法

• 当前选择
• 限制条件

• 终止条件

• 当前选择，只可以选当前对应数字的对应字符

• 限制条件，如上
• 终止条件，长度达到

其中我们需要有的paramteter

1. 当前对应的数字，所以要有digits和index
2. 限制条件，我们需要一个map去得到对应的字符
3. 终止条件，要知道长度

Solution

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

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        length = len(digits)
        self.length = length
        result = []
        self.combHelper(result, "", digits, 0)
        return result

    def combHelper(self, result, cur_str, digits, index):
        if len(cur_str) == self.length:
            result.append(cur_str)
            return
        val = int(digits[index])
        for c in self.c_map[val]:
            cur_str += c
            self.combHelper(result, cur_str, digits, index+1)
            cur_str = cur_str[:-1]

Reference