10/13 每日一題 (電話號碼的字母組合)

 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 digits 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'].

class Solution:

    def letterCombinations(self, digits: str) -> List[str]:

        my_dict={"2":list('abc'),'3':list('def'),'4':list('ghi'),'5':list('jkl'),'6':list('mno'),'7':list('pqrs'),'8':list('tuv'),'9':list('wxyz')}

        res=[]

        n=len(digits)

        if n<1:

            return []

        elif n==1:

            return my_dict[digits]

        elif n==2:    

            for i in my_dict[digits[0]]:

                for j in my_dict[digits[1]]:

                    string=i+j

                    res.append(string)

        elif n==3:    

            for i in my_dict[digits[0]]:

                for j in my_dict[digits[1]]:

                    for k in my_dict[digits[2]]:

                        string=i+j+k

                        res.append(string)

        else:

            for i in my_dict[digits[0]]:

                for j in my_dict[digits[1]]:

                    for k in my_dict[digits[2]]:

                        for l in my_dict[digits[3]]:

                            string=i+j+k+l

                            res.append(string)

       

       

        return res

--------------------

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = { "2": "abc", "3": "def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}

        res = []
        if len(digits) == 0:
            return res

    
        def helper(idx, res, curr_path):
            if idx == len(digits):
                res.append(curr_path)
                return
            for char in dic[digits[idx]]:
                helper(idx+1,res, curr_path+char)

        helper(0, res,"")
        return res