Letter Combinations of a Phone Number

Data Structures and Algorithms

Statement

Given a string containing digits from 2 to 9 inclusive, where digits can appear multiple times, return all possible letter combinations that the number could represent.

On a phone pad, digits map to letters as follows:

• 2 → (abc)
• 3 → (def)
• 4 → (ghi)
• 5 → (jkl)
• 6 → (mno)
• 7 → (pqrs)
• 8 → (tuv)
• 9 → (wxyz)

Constraints

• 0 ≤ digits.length() ≤ 4
• digits[i] is in the range [2, 9]

Solution

"""
production algorithm
"""


class Solution:
    def letter_combinations(self, digits):
        """
        time complexity O(n * k^n)
        space complexity O(nk)
        """
        if len(digits) == 0:
            return list()
        words = self.generate_words(digits)
        n, i = len(words), 0
        current, result = list(), list()
        self.letter_combinations_helper(words, n, i, current, result)
        return result

    def letter_combinations_helper(self, words, n, i, current, result):
        """
        time complexity O(n * k^n)
        space complexity O(n)
        """
        if i == n:
            result.append(str().join(current))
            return
        for character in words[i]:
            current.append(character)
            self.letter_combinations_helper(words, n, i + 1, current, result)
            current.pop()

    def generate_words(self, digits):
        """
        time complexity O(n)
        space complexity O(nk)
        """
        map = [None, None, "abc", "def", "ghi",
               "jkl", "mno", "pqrs", "tuv", "wxyz"]
        words = [map[int(d)] for d in digits]
        return words

"""
unit tests
"""

from unittest import TestCase
from algorithms.subsets.letter_combinations_of_phone_number.solution import Solution


class SolutionTestCase(TestCase):
    def test_empty_digits(self):
        # Given
        digits = ""
        solution = Solution()

        # When
        actual = solution.letter_combinations(digits)

        # Then
        expected = []
        self.assertEqual(actual, expected)

    def test_mixed_digits(self):
        # Given
        digits = "357"
        solution = Solution()

        # When
        actual = solution.letter_combinations(digits)

        # Then
        expected = ["djp", "djq", "djr", "djs",
                    "dkp", "dkq", "dkr", "dks",
                    "dlp", "dlq", "dlr", "dls",
                    "ejp", "ejq", "ejr", "ejs",
                    "ekp", "ekq", "ekr", "eks",
                    "elp", "elq", "elr", "els",
                    "fjp", "fjq", "fjr", "fjs",
                    "fkp", "fkq", "fkr", "fks",
                    "flp", "flq", "flr", "fls"]
        self.assertEqual(actual, expected)

Strategy

Subsets.

Explanation

The first step taken by the algorithm is to map all digits to letters. Then, backtracking is used to find all letter combinations. At each step of recursion in backtracking, an iteration of all letters of a digit takes place. As is done in backtracking, a letter is appended to the end of the current combination seen so far, a step of recursion is taken, and then afterwards the current letter is popped from the end of the current combination before the next iteration. At the maximum recursion depth when a combination has been found, then it’s appended to the result of all combinations.

Time Complexity

The algorithm of letter_combinations uses two helper functions, letter_combinations_helper and generate_words. The helper function generate_words iterates the length of the input digits, and so has time complexity O(n). The helper function letter_combinations_helper that’s used for recursion has a different time complexity.

Let n be the length of the input digits, and k be the length of the longest mapping of letters for some digit; e.g. 7 → (pqrs). At each step of recursion there’s k additional calls of recursion made, and the maximum depth of recursion is n. Therefore, there are k^n total letter combinations.

Now, for each letter combination, it must be copied and recorded. Doing so has time complexity O(n). Therefore, the time complexity of the helper function letter_combinations_helper is O(n * k^n).

Moreover, the time complexity of the algorithm letter_combinations is O(n * k^n).

Space Complexity

The auxiliary space complexity of the helper function generate_words depends on the number of digits n, and the length of the longest mapping of letters k. In other words, for each digit a string of maximum length k is added to the generated words. The generated words are used to find the solution but are not part of the solution. Therefore, the auxiliary space complexity of the helper function generate_words is O(nk).

Now, the auxiliary space complexity of the helper function letter_combinations_helper depends on the space that’s used to find the solution but isn’t part of the solution. The helper function doesn’t take additional auxiliary space for variables. However, as is the nature of recursion, it takes auxiliary space for the call stack. The maximum depth of recursion of the helper function is n. Therefore, the auxiliary space complexity of the helper function letter_combinations_helper is O(n).

Moreover, the auxiliary space complexity of the algorithm letter_combinations is O(nk).

Links

data_structures_algorithms/algorithms/subsets/letter_combinations_of_phone_number at main ·…