LeetCode 017 Letter Combinations of a Phone Number

LeetCode 017 Letter Combinations of a Phone Number

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 = "23"
**Output:** ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

**Input:** digits = ""
**Output:** []

Example 3:

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

Constraints:

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

题目大意：

在拨号键盘上按下了几个键，问能打出来的字符串的所有组合是多少。。

递归法解题思路：

DFS的典型题目。

与Java的区别：

1. 直接用Str作为临时结果，不需要用char array，因为str可以含有array的性质

注意事项：

1. 输入值为空的情况
2. 终止条件记得return
3. 用常量

Python代码：

DIGIT2CHAR = {
    '0': '',
    '1': '',
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

class Solution(TestCases):

    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        if digits == '':
            return result
        self.dfs(digits, 0, '', result, DIGIT2CHAR)
        return result

    def dfs(self, digits, start, path, result, DIGIT2CHAR):
        if start == len(digits):
            result.append(path)
            return
        for letter in DIGIT2CHAR[digits[start]]:
            self.dfs(digits, start + 1, path + letter, result, DIGIT2CHAR)

迭代法解题思路：

第二种方法，用迭代法，三种循环，输入数字串的每个数字，每个数字对应的字符加到当前的结果字符串列表中。

注意事项：

1. 要[‘’]而不是[]否则循环不会进行

def letterCombinations(self, digits: str) -> List[str]:
	if digits == '':
		return []
	result = ['']
	for d in digits:
		result = [s + c for s in result for c in DIGIT2CHAR[d]]
	return result

算法分析：

这是NP问题。时间复杂度为O(4n)，空间复杂度O(1)。