Letter Combinations of a Phone Number

---

Letter Combinations of a Phone Number: 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 2:

Input: digits = "2"
Output: ["a","b","c"]

---

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9']

---

Try this Problem on your own or check similar problems:

1. Combination Sum
2. Genarate Parentheses

Solution:

Java

class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()) return List.of();
        List<String> result = new ArrayList<>();
        List<List<Character>> mappings = List.of(
            List.of('a', 'b', 'c'),
            List.of('d', 'e', 'f'),
            List.of('g', 'h', 'i'),
            List.of('j', 'k', 'l'),
            List.of('m', 'n', 'o'),
            List.of('p', 'q', 'r', 's'),
            List.of('t', 'u', 'v'),
            List.of('w', 'x', 'y', 'z')
        );
        helper(digits, 0, mappings, new StringBuilder(), result);
        return result;
    }
    private void helper(String s, int index, List<List<Character>> mappings, StringBuilder currentString, List<String> result){
        if(s.length() == index){
          result.add(currentString.toString());
          return;
        }

        char c = s.charAt(index);
        List<Character> letters = mappings.get(c - '0' - 2);
        for(int i = 0; i < letters.size(); ++i){
            currentString.append(letters.get(i));
            helper(s, index + 1, mappings, currentString, result);
            currentString.setLength(currentString.length()-1);
        }
    }
}

JavaScript

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (!digits.length) return [];
  const mappings = [
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
    ["j", "k", "l"],
    ["m", "n", "o"],
    ["p", "q", "r", "s"],
    ["t", "u", "v"],
    ["w", "x", "y", "z"],
  ];
  const result = [];
  helper(digits, 0, mappings, "", result);
  return result;
};

function helper(s, index, mappings, currentString, result) {
  if (s.length === index) {
    result.push(currentString);
    return;
  }

  const letters = mappings[parseInt(s[index]) - 2];
  for (const letter of letters) {
    helper(s, index + 1, mappings, currentString + letter, result);
  }
}

Python

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        mappings = [
            ['a', 'b', 'c'],
            ['d', 'e', 'f'],
            ['g', 'h', 'i'],
            ['j', 'k', 'l'],
            ['m', 'n', 'o'],
            ['p', 'q', 'r', 's'],
            ['t', 'u', 'v'],
            ['w', 'x', 'y', 'z']
        ]
        result = []
        self.helper(digits, 0, mappings, "", result)
        return result

    def helper(self, s: str, index: int, mappings: List[List[str]], currentString: str, result: List[str]) -> None:
        if len(s) == index:
            result.append(currentString)
            return

        letters = mappings[int(s[index]) - 2]
        for letter in letters:
            self.helper(s, index + 1, mappings, currentString + letter, result)

C++

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> result;
        vector<vector<char>> mappings = {
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
        };
        helper(digits, 0, mappings, "", result);
        return result;
    }
    private:
    void helper(const string& s, int index, const vector<vector<char>>& mappings, string currentString, vector<string>& result) {
        if (s.length() == index) {
            result.push_back(currentString);
            return;
        }

        char c = s[index];
        vector<char> letters = mappings[c - '0' - 2];
        for (char letter : letters) {
            helper(s, index + 1, mappings, currentString + letter, result);
        }
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n*4^n)
• Space Complexity: O(n)

---

Explanation:

Common backtracking problem like we solved before, so we're using the same approach we did in almost all backtracking problems (check backtracking tagged questions Backtracking). We use helper mappings so we can map from digit to corresponding letters on the phone. Since arrays are zero indexed, and valid digits start from 2, we subtract 2 to get the right mapping. We loop over the letters and choose each one of them calling each time the helper function recursively until we reach the end of string (our base case). Recursion is n level deep and at each level we make at most 4 decisions leading to time complexity of O(n*4^n) (multiplier n for converting StringBuilder to regular string), with space complexity of O(n) accounting for recursion stack and the length of the candidates currentString.