Letter Combinations of a Phone Number medium

Problem Statement

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'

Example 1

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input: digits = "" Output: []

Steps

1. Base Case: If the input string digits is empty, return an empty list. This handles the case where there are no digits to process.

2. Mapping: Create a dictionary or array to map digits to their corresponding letters. This will make it easy to look up letters for each digit.

3. Recursive Approach (Backtracking): We'll use a recursive function to generate combinations.

   • The function will take the current combination being built (combination), the index of the digit being processed (digitIndex), and the list of digits (digits).
   • Base Case: If digitIndex reaches the end of the digits string, add the current combination to the result list and return.
   • Recursive Step: For the digit at digits[digitIndex], get its corresponding letters from the mapping. Iterate through these letters. For each letter:
     • Append the letter to the combination.
     • Recursively call the function with the updated combination and the next digitIndex.
     • Remove the letter from the combination (backtracking) to explore other possibilities.

4. Result: The recursive function will explore all possible combinations, and the result list will contain all the valid letter combinations.

Explanation

The solution uses backtracking, a powerful technique for exploring all possible solutions to a problem. Imagine a tree where each level represents a digit. Each branch at a level represents a letter corresponding to that digit. Backtracking systematically explores each branch, adding a letter to the current combination, and then removing it to explore other branches. This ensures we don't miss any possible combination.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public IList<string> LetterCombinations(string digits) {
        IList<string> result = new List<string>();
        if (string.IsNullOrEmpty(digits)) return result;

        Dictionary<char, string> mapping = new Dictionary<char, string>() {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };

        Backtrack(result, mapping, digits, 0, "");
        return result;
    }

    private void Backtrack(IList<string> result, Dictionary<char, string> mapping, string digits, int digitIndex, string combination) {
        if (digitIndex == digits.Length) {
            result.Add(combination);
            return;
        }

        char digit = digits[digitIndex];
        string letters = mapping[digit];
        foreach (char letter in letters) {
            Backtrack(result, mapping, digits, digitIndex + 1, combination + letter);
        }
    }
}

Complexity

• Time Complexity: O(4^N * N), where N is the length of the input digits string. In the worst case, each digit can map to 4 letters, and we need to construct combinations of length N. The N factor comes from string concatenation in each recursive call.

• Space Complexity: O(N) due to the recursive call stack. The space used by the result list is also proportional to the number of combinations, which is bounded by O(4^N).