• 1

• 2.5k
• 2
• 28
• 51

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); 
 }
 }
 }
}