首页 > itarticle > leetcode 017

leetcode 017

admin 11月 13, 2020 0

Letter Combinations of a Phone Number
Method
Python Code

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

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.

Method

Use the DFS algorithm to search all the combination.

Python Code

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        if not digits:
            return []
        result = []
        self.dfs(digits, "", result)
        return result
        
    def dfs(self,digits,current,result):
        if not digits:
            result.append(current)
            return
        for c in self.ddict[digits[0]]:
            self.dfs(digits[1:],current+c,result)
    

    ddict = {'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']
    }