unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 17: Letter Combinations of a Phone Number

link

Recursive

Letter combinations of “23” is the cartesian product of corresponding letter sets: {“a”, “b”, “c”} and {“d”, “e”, “f”}.

Note, there can be at most four different letters for a digit.

Time: \mathcal{O}(4^n \cdot n), space: \mathcal{O}(n).

class Solution:
    def collect(self, i, digits, curr, combinations, letter_map):
        if i == len(digits):
            combinations.append( "".join(curr) )
            return
        
        for c in letter_map[digits[i]]:
            curr.append(c)
            self.collect(i+1, digits, curr, combinations, letter_map)
            curr.pop()

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

        # 23: [a b c] X [d e f]
        letter_map = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }

        comb = []
        self.collect(0, digits, [], comb, letter_map)

        return comb

Iterative

For each possible letter for a new digit, we can append it to each of the earlier combinations to have extended combinations.

Time: \mathcal{O}(4^n \cdot n), space: \mathcal{O}(n).

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        # 23: [a b c] X [d e f]
        # [""]
        # ["a", "b", "c"]
        # ["ad", "bd", "cd", "ae", "be", "ce", "af", "bf", "cf"]
        letter_map = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }

        combinations = [""]
        for d in digits:
            tmp = []
            for c in letter_map[d]:
                for comb in combinations:
                    tmp.append( comb+c )
            combinations = tmp

        return combinations

tanvirdotzaman

,

Leave a comment