Problem Statement: Letter Combinations of a Phone Number
Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on the telephone buttons) is given below.
2maps to["a", "b", "c"]3maps to["d", "e", "f"]4maps to["g", "h", "i"]5maps to["j", "k", "l"]6maps to["m", "n", "o"]7maps to["p", "q", "r", "s"]8maps to["t", "u", "v"]9maps to["w", "x", "y", "z"]
The output should return all possible combinations of letters that can be formed by the digits in the input string.
Example:
Input:
digits = "23"
Output:
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Input:
digits = ""
Output:
[]
Input:
digits = "2"
Output:
["a", "b", "c"]
Approach:
The problem can be approached by using backtracking or iterative combination generation. We can build the combinations step by step by taking one letter from each digit’s corresponding character set.
- Backtracking:
- Start with the first digit, and for each letter corresponding to the digit, recursively proceed to the next digit, adding the current letter to the combination.
- Once all digits have been processed, store the combination.
- Iterative Combination:
- Start with an empty combination list, and for each digit, iterate over the current combinations and append the new letters that correspond to the digit.
- This is similar to performing a Cartesian product across the characters of each digit.
Steps:
- Map Digits to Letters: Use a dictionary to map each digit to its corresponding letters.
- Use Backtracking or Iteration: For each digit, either generate combinations using recursion or iteratively build them.
- Edge Cases:
- If the input is an empty string, return an empty list.
- Handle input strings with multiple digits.
Time Complexity:
- Time Complexity: O(3N)O(3^N)O(3N), where NNN is the number of digits in the input. In the worst case, each digit can map to 4 letters, so the number of combinations grows exponentially with the length of the string.
- Space Complexity: O(3N)O(3^N)O(3N) for storing the result, plus the recursion stack in case of backtracking.
Code Implementation
C Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const char* digitToChar[] = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
void backtrack(char* digits, int index, char* current, char** result, int* returnSize) {
if (index == strlen(digits)) {
result[*returnSize] = (char*)malloc(strlen(current) + 1);
strcpy(result[*returnSize], current);
(*returnSize)++;
return;
}
int digit = digits[index] - '0';
for (int i = 0; i < strlen(digitToChar[digit]); i++) {
current[index] = digitToChar[digit][i];
backtrack(digits, index + 1, current, result, returnSize);
}
}
char** letterCombinations(char* digits, int* returnSize) {
if (digits == NULL || strlen(digits) == 0) {
*returnSize = 0;
return NULL;
}
char** result = (char**)malloc(1000 * sizeof(char*)); // Assumption of max size
char* current = (char*)malloc(strlen(digits) + 1);
*returnSize = 0;
backtrack(digits, 0, current, result, returnSize);
free(current);
return result;
}
int main() {
char digits[] = "23";
int returnSize;
char** result = letterCombinations(digits, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
free(result[i]);
}
free(result);
return 0;
}
C++ Code:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
if (digits.empty()) return result;
vector<string> digitToChar = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
string current;
backtrack(digits, 0, current, result, digitToChar);
return result;
}
private:
void backtrack(const string& digits, int index, string& current, vector<string>& result, const vector<string>& digitToChar) {
if (index == digits.size()) {
result.push_back(current);
return;
}
int digit = digits[index] - '0';
for (char c : digitToChar[digit]) {
current.push_back(c);
backtrack(digits, index + 1, current, result, digitToChar);
current.pop_back();
}
}
};
int main() {
Solution solution;
vector<string> result = solution.letterCombinations("23");
for (const string& combination : result) {
cout << combination << endl;
}
return 0;
}
Java Code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
private static final String[] DIGIT_TO_CHAR = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.isEmpty()) return result;
StringBuilder current = new StringBuilder();
backtrack(digits, 0, current, result);
return result;
}
private void backtrack(String digits, int index, StringBuilder current, List<String> result) {
if (index == digits.length()) {
result.add(current.toString());
return;
}
int digit = digits.charAt(index) - '0';
for (char c : DIGIT_TO_CHAR[digit].toCharArray()) {
current.append(c);
backtrack(digits, index + 1, current, result);
current.deleteCharAt(current.length() - 1); // Backtrack
}
}
public static void main(String[] args) {
Solution solution = new Solution();
List<String> result = solution.letterCombinations("23");
for (String combination : result) {
System.out.println(combination);
}
}
}
Python Code:
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
digit_to_char = [
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
]
result = []
self._backtrack(digits, 0, "", result, digit_to_char)
return result
def _backtrack(self, digits: str, index: int, current: str, result: List[str], digit_to_char: List[str]):
if index == len(digits):
result.append(current)
return
digit = int(digits[index])
for char in digit_to_char[digit]:
self._backtrack(digits, index + 1, current + char, result, digit_to_char)
# Example usage
solution = Solution()
print(solution.letterCombinations("23"))
C# Code:
using System;
using System.Collections.Generic;
public class Solution {
private static readonly string[] DigitToChar = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public IList<string> LetterCombinations(string digits) {
var result = new List<string>();
if (string.IsNullOrEmpty(digits)) return result;
Backtrack(digits, 0, "", result);
return result;
}
private void Backtrack(string digits, int index, string current, IList<string> result) {
if (index == digits.Length) {
result.Add(current);
return;
}
int digit = digits[index] - '0';
foreach (char c in DigitToChar[digit]) {
Backtrack(digits, index + 1, current + c, result);
}
}
public static void Main() {
Solution solution = new Solution();
var result = solution.LetterCombinations("23");
foreach (var combination in result) {
Console.WriteLine(combination);
}
}
}
JavaScript Code:
var letterCombinations = function(digits) {
if (digits === "") return [];
const digitToChar = [
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
];
let result = [];
function backtrack(index, current) {
if (index === digits.length) {
result.push(current);
return;
}
let digit = digits[index] - '0';
for (let char of digitToChar[digit]) {
backtrack(index + 1, current + char);
}
}
backtrack(0, "");
return result;
};
// Example usage
console.log(letterCombinations("23"));
Explanation:
- Mapping Digits to Characters: We have an array (or dictionary) that maps digits to their corresponding letters.
- Backtracking: We start from the first digit, pick each character from the corresponding string, and recursively try all combinations for the next digit.
- Edge Case Handling: If the input string is empty, we return an empty list.
Time Complexity:
- Time Complexity: O(3^N)) in the worst case, where NNN is the number of digits in the input. Each digit can have 3 or 4 characters (depending on the digit).
- Space Complexity: O(3^N) for storing the combinations.