Leetcode 17. Letter Combinations of a Phone Number

Question

Problem Statement

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input: Digit string "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

My explanation of algorithm

I spent more than one hour to review my last practice, and like to ask code review for C# code.

Highlights of change

1. Use meaningful variable names
2. the depth first search function has 5 arguments, I chose to order the arguments using 3 categories, input, DFS helper, output.
3. Use var explicit typing when possible.
4. Add two test cases.

I am not sure if variable names can be named better, and 5 arguments in depth first search function RunDepthFirstSearch can be replaced by better implementation.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _17LetterCombinationOfAPhoneNUmber_DFS
{
/*
 * Leetcode 17:
 * https://leetcode.com/problems/letter-combinations-of-a-phone-number/
 * Given a digit string, return all possible letter combinations that 
 * the number could represent.
   A mapping of digit to letters (just like on the telephone buttons) is given below.
 * Input:Digit string "23"
   Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * 
 * Telephone dial pad:
 *                     0  1   2     3     4     5     6     7      8     9 
 * String[] keyboard={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 */
  class Solution
  {
    static void Main(string[] args)
    {
        RunTestcase(); 
    }

    public static void RunTestcase()
    {
        // test result: "abc", "def", so 3x3 = 9 cases.
        IList<string> letterCombinations = LetterCombination("23");             
        Debug.Assert(letterCombinations.Count == 9);

        IList<string> letterCombinations2 = LetterCombination("2345678");             
        Debug.Assert(letterCombinations.Count == 9*9*3); 
    }

    public static IList<string> LetterCombination(string digitString)
    {
        var letterCombinations = new List<string>();
        if (digitString == null || digitString.Length == 0)
            return letterCombinations;

        var keyboard = new string[]{ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

        var builder = new StringBuilder();
        RunDepthFirstSearch(keyboard, digitString, 0, builder, letterCombinations);  

        return letterCombinations;
    }

    /*                  
     * keyboard = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
     * 
     * input arguments: 
     * @keyboard
     * @digitString
     * 
     * helper to track DFS steps, the index of digitString, and intermediate result
     * @scanIndex - scan digitString. Go over digitString, scan chars from 
     *              left to right one by one. 
     * @letterCombination
     * 
     * output arguments: 
     * @letterCombinations
     * 
     * Because there are 5 arguments, order the arguments using input, DFS helpers, 
     * and output arguments.
     * 
     * For each digit, apply depth first search and backtrack through chars in keyboard. 
     * For example, digitString "23", the first char 2 maps to "abc".
     * Do not forget to backtrack.  
     */
    private static void RunDepthFirstSearch(
        string[]      keyboard,
        string        digitString,
        int           scanIndex,
        StringBuilder letterCombination,
        IList<string> letterCombinations                                             
        )
    {
        if (letterCombination.Length == digitString.Length)
        {
            letterCombinations.Add(letterCombination.ToString());
            return;
        }

        // work on first case, first char in digits array
        var  keyboardIndex = digitString[scanIndex] - '0';
        var  letters = keyboard[keyboardIndex];

        for (int i = 0; i < letters.Length; i++)
        {
            // work on one char a time
            char currentChar = letters[i];                

            // DFS step 
            letterCombination.Append(currentChar);
            RunDepthFirstSearch(keyboard, digitString,  scanIndex + 1, letterCombination, letterCombinations);

            // remove last char - backtracking
            letterCombination.Remove(letterCombination.Length - 1, 1); 
        }
    }
  }
}

Answer 1

To use only static methods increases complexity of your code (because you need more parameters for function calls). In this review I won't change this to do not go to far away from your original code but you should also give it a try (for more complex code you will see a huge difference.)

First of all let's move algorithm to a separate class:

static class PhoneKeyboard {
    public static IEnumerable<string> FindAllWordsForNumber(string digits) {
       // ...
    }
}

Keyboard layout won't change then you should make keyboard a private static field, you won't even need it as parameter.

private static readonly string[] Keyboard = // ...

An empty digit parameter is a corner case for which I wouldn't perform any special optimization, let's go through the normal code and return an empty list. Note that your original code may be simplified using String.IsNullOrEmpty() or String.IsNullOrWhiteSpace() (see MSDN for details.) However a null input is wrong and I don't want to swallow a possible bug in calling code:

if (digits == null)
    throw new ArgumentNullException(nameof(digits));

Main code is then just:

var combinations = new List<string>();
CombineDigitWithAllSubsequentDigits(digits, 0, new StringBuilder(), combinations);

Where CombineDigitWithAllSubsequentDigits() is, so far, your original code in RunDepthFirstSearch() (I changed name because it's a recursive function, it's not a first search but this is just my POV.) Few changes here, I'd keep the StringBuilder trick (but I'd add few comments about its usage because it's not obvious at first sight.)

Condition letterCombination.Length == digitString.Length isn't clear, you should introduce a local boolean to explain its meaning and also consider to use scanIndex for comparison (because it conveys more meaning about what your're checking):

bool isEndOfString = scanIndex == digits.Length;
if (isEndOfString) {
   // ...
}

I'd also consider to move it inside your for loop for clarity but for the moment just keep it there. Do not forget to validate input and move that string-to-number conversion into a separate function:

static int ParseKeyboardDigit(char c)
{
    int digit = c - '0';
    if (digit < 0 || digit >= Keyboard.Length)
        throw new ArgumentException($"Character {c} is not a digit.");

    return digit;
}

Your loop may be simplified little bit using foreach (you do not actually use index) and to trim last character of a StringBuilder you can simply change its Length property (slightly faster but the point is that IMO it's more clear the intent).

int digit = ParseKeyboardDigit(digits[scanIndex]);
foreach (var character in Keyboard[digit])
{
    currentCombination.Append(character);
    CombineDigitWithAllSubsequentDigits(digits, scanIndex + 1,
        currentCombination, combinations);

    // Trim last character for the next one in the loop
    --currentCombination.Length;
}

Side notes: you shouldn't test only for the number of produced combinations but also for their content. It's tedious but it's the only way to be sure about your algorithm. Also, your tests shouldn't be tied inside the same class where you implement your algorithm but outside (possibly in a separate assembly for unit testing...)