Sponsored
Sponsored
This approach uses recursion to explore all possible combinations represented by the digit-to-letter mapping of a phone keypad. We incrementally build letter combinations by allocating one letter per digit, and then explore further by making recursive calls.
The recursion depth is determined by the number of digits and the choices per digit. At each step, the algorithm branches into as many recursive calls as there are letters assigned to the current digit, continuing until all digits have been processed.
Time Complexity: O(3^n * 4^m), where n is the number of digits that map to 3 letters, and m is the number of digits that map to 4 letters.
Space Complexity: O(n), the maximum depth of the recursion stack is n.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<string> LetterCombinations(string digits) {
6 if (digits.Length == 0) return new List<string>();
7 string[] phoneMap = new string[] {
8 "", "", "abc", "def",
9 "ghi", "jkl", "mno",
10 "pqrs", "tuv", "wxyz"
11 };
12 var combinations = new List<string>();
13 Backtrack(combinations, phoneMap, digits, new char[digits.Length], 0);
return combinations;
}
private void Backtrack(IList<string> combinations, string[] phoneMap, string digits, char[] path, int index) {
if (index == digits.Length) {
combinations.Add(new string(path));
return;
}
string possibleLetters = phoneMap[digits[index] - '0'];
foreach (char letter in possibleLetters) {
path[index] = letter;
Backtrack(combinations, phoneMap, digits, path, index + 1);
}
}
public static void Main(string[] args) {
Solution sol = new Solution();
var result = sol.LetterCombinations("23");
foreach (var combination in result) {
Console.WriteLine(combination);
}
}
}In this C# solution, a recursive method is used to construct combinations similarly to the other solutions. The path char array captures current state of combination development, with each digit's possible letters iteratively being explored via recursion.
The iterative BFS approach systematically explores all possible combinations of letter sequences by progressively building up combinations using a queue. It starts by enqueueing an empty string, and then, for each digit from the input, extends through all mapped letters, enqueuing partial solutions until all digits have been processed.
This method mimics the complete depth-first search but layers on combinations iteratively, capitalizing on the breadth search over immediate digit map expansion.
Time Complexity: O(3^n * 4^m), as methodically layers through the digit-letter expansion uniformly across a queue.
Space Complexity: O(n * 3^n * 4^m), where queue storage inflates in tandem with combination depth.
using System.Collections.Generic;
public class Solution {
public IList<string> LetterCombinations(string digits) {
List<string> combinations = new List<string>();
if (digits.Length == 0) return combinations;
string[] phoneMap = new string[] {
"", "", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"
};
Queue<string> queue = new Queue<string>();
queue.Enqueue("");
foreach (char digit in digits.ToCharArray()) {
int levelSize = queue.Count;
for (int i = 0; i < levelSize; i++) {
string prevCombination = queue.Dequeue();
foreach (char letter in phoneMap[digit - '0'].ToCharArray()) {
queue.Enqueue(prevCombination + letter);
}
}
}
while (queue.Count != 0) {
combinations.Add(queue.Dequeue());
}
return combinations;
}
public static void Main(string[] args) {
Solution sol = new Solution();
var result = sol.LetterCombinations("23");
foreach (var combination in result) {
Console.WriteLine(combination);
}
}
}The C# version integrates queue mechanics to navigate valid letter combinations by adding and removing segments iteratively. Its result is built through background enqueuing, revealing comprehensive digit pairings post-traversal.