Letter Combination

Question

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.

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

Input: digits = ""
Output: []

Input: digits = ""
Output: []

Solution

Normal bruteforce

The idea is we just have a for loop to combine with the current result in our array.

class App:
    def __init__(self):
        self.numberToString = {
            "0": [],
            "1": [],
            "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"],
        }
        
    def letterCombination(self, s: str) -> List[str]:
        result = []
        
        for num in s:
            if not result:
                result = self.numberToString[num].copy()
            else:
                newResult = self.combine(self.numberToString[num], result)
                if (newResult):
                    result = newResult
            
        return result

    def combine(self, characterList: List[str], resultArray: List[str]):
        if not characterList or not resultArray: return
        
        newResult = []
        
        for result in resultArray:
            for character in characterList:
                newResult.append(result + character)
        
        return newResult

Time complexity: $O(length \times 4 \times resultLength)$
Space complexity: $O(length \times 4^n)$

• 4 is because one maximum we can have 4 characters in a number (as number 7). So if we have 7777, it will be 4 x 4 x 4 x 4 = $4^n$

Backtracking

The idea is we have to explore out from the first index. And then we can keep continue from next and next index.

class App:
    def __init__(self):
        self.numberToString = {
            "0": [],
            "1": [],
            "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"],
        }

    def letterCombinations(self, s: str) -> List[str]:
        if not s: return []
        self.result = []
        self._letterCombinations([], 0, s)
        return self.result
    
    def _letterCombinations(self, currentString: List[str], currentIndex: int, s: str):
        if len(currentString) > 0 and (currentIndex == len(s) or currentIndex < len(s) and not self.numberToString[s[currentIndex]]):
            self.result.append("".join(currentString))
            return
            
        for letter in self.numberToString[s[currentIndex]]: # a, b, c
            currentString.append(letter)
            self._letterCombinations(currentString, currentIndex + 1, s)
            currentString.pop()

In here the if condition check:

if (currentIndex == len(s) or currentIndex < len(s) and not self.numberToString[s[currentIndex]]):

Is for the scenario that:

1. We can form all the string of correct length (currentIndex == len(s))
2. We can form a string of not correct length but there is nothing else to form (e.g 12)

Time complexity: $O(4^n)$
Space complexity: $O(4^n)$