LeetCode 17 - Letter Combinations of a Phone Number

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.

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"]

Answer:

The problem requires finding all possible letter combinations that can be formed by a given sequence of digits. For example, if the input is "23", then the output should contain all possible combinations of the letters 'a', 'b', and 'c' for digit 2, and 'd', 'e', and 'f' for digit 3. This can be solved using a backtracking approach where we start with the first digit and find all the possible letters that can be formed using that digit, and then move on to the next digit and find all the possible letters that can be formed using that digit, and so on until we have formed a combination of all digits.

Approach:

Define a function letterCombinations which takes a string of digits as input and returns a vector of all possible letter combinations.
Check if the input string is empty, if it is, return an empty vector as there are no possible letter combinations.
Define a mapping vector which contains the letters corresponding to each digit. For example, the mapping vector for the input "23" would be {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}.
Define an empty string combination with the same size as the input digits string.
Call the backtrack function with the initial index as 0 and pass the result vector, mapping vector, combination string, and digits string as arguments.
In the backtrack function, check if the current index is equal to the size of the digits string. If it is, that means we have formed a complete combination of letters, so we add the current combination string to the result vector and return.
Otherwise, get the possible letters corresponding to the current digit using the mapping vector.
Iterate through all the possible letters and set the current index of the combination string to that letter.
Call the backtrack function recursively with the incremented index.
After the recursive call returns, reset the current index of the combination string to its previous value so that we can try the next letter.

Time Complexity:

The time complexity of the algorithm is O(3^N × 4^M), where N is the number of digits in the input string that correspond to 3 letters ('2', '3', '4', '5', '6', '8'), and M is the number of digits in the input string that correspond to 4 letters ('7', '9'). The reason for this is that each digit can correspond to 3 or 4 letters, and we need to generate all possible combinations of these letters. The maximum length of the result vector can be 3^N × 4^M, as each letter can be used at most once in a combination.

Space Complexity:

The space complexity of the algorithm is O(N), where N is the number of digits in the input string. This is because we use a combination string of size N to store the current combination of letters being formed, and a result vector to store all the possible combinations. The mapping vector is of constant size and does not contribute to the space complexity.

Code:

class Solution(object):
    def letterCombinations(self, digits):
        result = []
        if not digits:
            return result
        mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        combination = [""] * len(digits)
        self.backtrack(result, mapping, combination, digits, 0)
        return result

    def backtrack(self, result, mapping, combination, digits, index):
        if index == len(digits):
            result.append("".join(combination))
        else:
            letters = mapping[int(digits[index])]
            for letter in letters:
                combination[index] = letter
                self.backtrack(result, mapping, combination, digits, index + 1)