(Medium #17) Letter Combinations of a Phone Number

Problem

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

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

My solution

class Solution:
    def twoCombinations(self, chlist1, chlist2):        
        output = []
        for i in range(len(chlist1)):
            ch1 = chlist1[i]
            for k in range(len(chlist2)):
                ch2 = chlist2[k]
                output.append(ch1+ch2)
            
        return output
        
    
    def letterCombinations(self, digits: str) -> List[str]:
        output = []
        
        if len(digits) == 0:
            return []
        
        digitchr = {}
        chrlist = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        for i, ch in enumerate(chrlist):
            digitchr[i+2] = ch        
        
        numlist = []
        for m in range(len(digits)):
            numlist.append(digitchr[int(digits[m])])
        
        previouslist = numlist[0]        
        for m in range(1, len(numlist)):
            previouslist = self.twoCombinations(previouslist, numlist[m])        
            
        return previouslist      

Runtime: 32ms, Memory: 13.7MB

Other people solution

class Solution:
    def letterCombinations(self, digits):
        if not digits:
            return []
        dic = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        res = []
        self.dfs(digits, dic, 0, "", res)
        return res

    def dfs(self, digits, dic, index, path, res):
        if len(path) == len(digits):
            res.append(path)
            return 
        for i in range(index, len(digits)):
            for j in dic[digits[i]]:
                self.dfs(digits, dic, i+1, path+j, res)

Runtime: 40ms, Memory: 13.9MB