Letter Combinations of a Phone Number

Every word a string of phone-keypad digits could spell, one letter per digit.

The idea

Handle one digit at a time. Look up the letters that digit maps to, and for each one, append it to the path so far and recurse on the next digit. Once every digit has contributed a letter, the path is a complete word to record.

Code

static readonly string[] Map = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

public static void Letters(string digits, int idx, string path, List<string> result) {
    if (idx == digits.Length) { result.Add(path); return; }
    string letters = Map[digits[idx] - '0'];
    if (letters == "") { Letters(digits, idx + 1, path, result); return; }
    for (int i = 0; i < letters.Length; i++)
        Letters(digits, idx + 1, path + letters[i], result);
}

Tips

• A digit with no letters (like 1) just passes the path through unchanged instead of branching: it never adds a character.
• There is no explicit undo here either, for the same reason as Generate Parentheses: path + letters[i] builds a new string per branch rather than mutating a shared one.

In the .NET library

Map[digits[idx] - '0'] turns a character digit straight into an array index. It is the same trick as bits[v.toString(2)] in reverse: subtracting the character code of '0' converts a digit character to its numeric value.