17. Letter Combinations of a Phone Number LeetCode Solution

In this guide we will provide 17. Letter Combinations of a Phone Number LeetCode Solution with best time and space complexity. The solution to Letter Combinations of a Phone Number problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Letter Combinations of a Phone Number solution in C++
Letter Combinations of a Phone Number soution in Java
Letter Combinations of a Phone Number solution Python
Additional Resources

17. Letter Combinations of a Phone Number LeetCode Solution image

Problem Statement of 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 3:

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

Constraints:

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

Complexity Analysis

Time Complexity: O(n4^n)
Space Complexity: O(4^n)

17. Letter Combinations of a Phone Number LeetCode Solution in C++

class Solution {
 public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty())
      return {};

    vector<string> ans;

    dfs(digits, 0, "", ans);
    return ans;
  }

 private:
  const vector<string> digitToLetters{"",    "",    "abc",  "def", "ghi",
                                      "jkl", "mno", "pqrs", "tuv", "wxyz"};

  void dfs(const string& digits, int i, string&& path, vector<string>& ans) {
    if (i == digits.length()) {
      ans.push_back(path);
      return;
    }

    for (const char letter : digitToLetters[digits[i] - '0']) {
      path.push_back(letter);
      dfs(digits, i + 1, std::move(path), ans);
      path.pop_back();
    }
  }
};
/* code provided by PROGIEZ */

17. Letter Combinations of a Phone Number LeetCode Solution in Java

class Solution {
  public List<String> letterCombinations(String digits) {
    if (digits.isEmpty())
      return new ArrayList<>();

    List<String> ans = new ArrayList<>();

    dfs(digits, 0, new StringBuilder(), ans);
    return ans;
  }

  private static final String[] digitToLetters = {"",    "",    "abc",  "def", "ghi",
                                                  "jkl", "mno", "pqrs", "tuv", "wxyz"};

  private void dfs(String digits, int i, StringBuilder sb, List<String> ans) {
    if (i == digits.length()) {
      ans.add(sb.toString());
      return;
    }

    for (final char c : digitToLetters[digits.charAt(i) - '0'].toCharArray()) {
      sb.append(c);
      dfs(digits, i + 1, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}
// code provided by PROGIEZ

17. Letter Combinations of a Phone Number LeetCode Solution in Python

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

    digitToLetters = ['', '', 'abc', 'def', 'ghi',
                      'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
    ans = []

    def dfs(i: int, path: list[str]) -> None:
      if i == len(digits):
        ans.append(''.join(path))
        return

      for letter in digitToLetters[int(digits[i])]:
        path.append(letter)
        dfs(i + 1, path)
        path.pop()

    dfs(0, [])
    return ans
 #code by PROGIEZ