Description:
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.
Examples:
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"]Solution in Python:
To solve the problem of generating all possible letter combinations that the given digits could represent (like on a telephone keypad), we can use a backtracking approach. This approach will allow us to efficiently explore all possible combinations of letters for the given digits.
Python
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# Mapping of digits to corresponding letters on a telephone button
digit_to_letters = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
# Resultant list to store the combinations
result = []
# Edge case: if the input digits string is empty, return an empty list
if not digits:
return result
# Helper function for backtracking
def backtrack(index: int, current_combination: str):
# If the current combination length equals the digits length, add to result
if index == len(digits):
result.append(current_combination)
return
# Get the letters corresponding to the current digit
current_digit = digits[index]
letters = digit_to_letters[current_digit]
# Iterate over the letters and call backtrack recursively
for letter in letters:
backtrack(index + 1, current_combination + letter)
# Start the backtracking process from index 0 and an empty combination
backtrack(0, "")
return resultExplanation:
- Mapping of Digits to Letters:
- We create a dictionary
digit_to_lettersthat maps each digit from ‘2’ to ‘9’ to its corresponding letters as found on a telephone button.
- We create a dictionary
- Edge Case Handling:
- If the input
digitsstring is empty, we return an empty list immediately since there are no digits to process.
- If the input
- Backtracking Function:
- We define a helper function
backtrackthat takes two parameters:indexandcurrent_combination. indexkeeps track of the current position in thedigitsstring that we are processing.current_combinationis the current combination of letters we have built so far.
- We define a helper function
- Base Case:
- If the
current_combinationlength is equal to the length of thedigitsstring, we add thecurrent_combinationto theresultlist because we have formed a valid combination.
- If the
- Recursive Case:
- We get the current digit using
digits[index]. - We retrieve the corresponding letters from the
digit_to_lettersdictionary. - We iterate over each letter and recursively call
backtrack, incrementing theindexand appending the current letter tocurrent_combination.
- We get the current digit using
- Initiate Backtracking:
- We start the backtracking process by calling
backtrack(0, "")withindexset to 0 andcurrent_combinationas an empty string.
- We start the backtracking process by calling
Solution in Javascript:
JavaScript
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
// Mapping of digits to corresponding letters on a telephone button
const digitToLetters = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
};
// Resultant array to store the combinations
const result = [];
// Edge case: if the input digits string is empty, return an empty array
if (digits.length === 0) {
return result;
}
// Helper function for backtracking
function backtrack(index, currentCombination) {
// If the current combination length equals the digits length, add to result
if (index === digits.length) {
result.push(currentCombination);
return;
}
// Get the letters corresponding to the current digit
const currentDigit = digits[index];
const letters = digitToLetters[currentDigit];
// Iterate over the letters and call backtrack recursively
for (let letter of letters) {
backtrack(index + 1, currentCombination + letter);
}
}
// Start the backtracking process from index 0 and an empty combination
backtrack(0, "");
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> letterCombinations(String digits) {
// Mapping of digits to corresponding letters on a telephone button
String[] digitToLetters = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
// Resultant list to store the combinations
List<String> result = new ArrayList<>();
// Edge case: if the input digits string is empty, return an empty list
if (digits.length() == 0) {
return result;
}
// Helper function for backtracking
backtrack(result, digitToLetters, digits, 0, new StringBuilder());
return result;
}
private void backtrack(List<String> result, String[] digitToLetters, String digits, int index, StringBuilder currentCombination) {
// If the current combination length equals the digits length, add to result
if (currentCombination.length() == digits.length()) {
result.add(currentCombination.toString());
return;
}
// Get the letters corresponding to the current digit
char currentDigit = digits.charAt(index);
String letters = digitToLetters[currentDigit - '0'];
// Iterate over the letters and call backtrack recursively
for (char letter : letters.toCharArray()) {
currentCombination.append(letter);
backtrack(result, digitToLetters, digits, index + 1, currentCombination);
currentCombination.deleteCharAt(currentCombination.length() - 1);
}
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<string> LetterCombinations(string digits) {
// Mapping of digits to corresponding letters on a telephone button
string[] digitToLetters = new string[] {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
// Resultant list to store the combinations
List<string> result = new List<string>();
// Edge case: if the input digits string is empty, return an empty list
if (digits.Length == 0) {
return result;
}
// Helper function for backtracking
void Backtrack(int index, string currentCombination) {
// If the current combination length equals the digits length, add to result
if (currentCombination.Length == digits.Length) {
result.Add(currentCombination);
return;
}
// Get the letters corresponding to the current digit
char currentDigit = digits[index];
string letters = digitToLetters[currentDigit - '0'];
// Iterate over the letters and call backtrack recursively
foreach (char letter in letters) {
Backtrack(index + 1, currentCombination + letter);
}
}
// Start the backtracking process from index 0 and an empty combination
Backtrack(0, "");
return result;
}
}