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.
方法一：标准正向递归，num == length时才append
class Solution(object): def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ def helper(num, string): if (num == length): res.append(string) else: for ls in dic[digits[num]]: helper(num+1, string+ls) res = [] dic = { ‘2‘:[‘a‘,‘b‘,‘c‘], ‘3‘:[‘d‘,‘e‘,‘f‘], ‘4‘:[‘g‘,‘h‘,‘i‘], ‘5‘:[‘j‘,‘k‘,‘l‘], ‘6‘:[‘m‘,‘n‘,‘o‘], ‘7‘:[‘p‘,‘q‘,‘r‘,‘s‘], ‘8‘:[‘t‘,‘u‘,‘v‘], ‘9‘:[‘w‘,‘x‘,‘y‘,‘z‘] } length = len(digits) if (length == 0): return [] helper(0, ‘‘) return res
方法二：temp临时值传值，python需要用res = copy.copy(tmp）
class Solution(object): ‘‘‘ 题意：输出电话号码对应的所有可能的字符串 可以递归或直接模拟 ‘‘‘ def letterCombinations(self, digits): chr = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] res = [] for i in range(0, len(digits)): num = int(digits[i]) tmp = [] for j in range(0, len(chr[num])): if len(res): for k in range(0, len(res)): tmp.append(res[k] + chr[num][j]) else: tmp.append(str(chr[num][j])) res = copy.copy(tmp) return res
Letter Combinations of a Phone Number
原文：http://www.cnblogs.com/hafgyyb/p/7113535.html