Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 26, 2016 19:33
Show Gist options
  • Save jianminchen/b866a5c331556ea8f36aecfe123befea to your computer and use it in GitHub Desktop.
Save jianminchen/b866a5c331556ea8f36aecfe123befea to your computer and use it in GitHub Desktop.
Leetcode 17 - phone number combination - need to work on the code, remove if/ else statement, make the code more flat.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _17LetterCombinationOfAPhoneNUmber_DFS
{
/*
* Leetcode 17:
* 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)
{
IList<string> list = letterCombination("23");
// test result: "abc", "def", so 3x3 = 9 cases.
}
public static IList<string> letterCombination(string digits)
{
IList<string> list = new List<string>();
if (digits == null || digits.Length == 0)
return list;
string[] keyboard = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
StringBuilder sb = new StringBuilder();
buildResult(list, keyboard, digits, sb, 0); // think about design here
return list;
}
/*
* Julia's practice on April 26, 2016
* Need to rewrite to get more experience.
* 2nd practice:
* Lessons learned:
* 1. Use another tmpS variable to save StringBuilder variable for next iteration
*
* Static analysis notes:
* 1. line 70, 71, use explanation variables c, s1,
* 2. miss the bug -
* line 68: index < len, not "len - 1",
* Julia, you have to allow the string complete, then, add it to the list.
* 3. add simple test case next to the function argument, help to complete the coding.
*
* one more note:
* Add basic case - when the string is ready to output and then add to the list.
* This way, the code is more easy to read and understand.
*
*/
private static void buildResult(
IList<string> list,
string[] keyboard,
string digits, // test case: "23"
StringBuilder yourOutput,
int index) // test case: "23", index value 0 and 1
{
// need to do the backtracking, need to do the recursive solution
if (index == digits.Length)
{
// add to the list
list.Add(yourOutput.ToString());
return;
}
char c = digits[index];
string s1 = keyboard[c - '0'];
foreach (char nextChar in s1)
{
string tmpS = yourOutput.ToString();
yourOutput.Append(nextChar);
buildResult(list, keyboard, digits, yourOutput, index + 1);
yourOutput = new StringBuilder(tmpS);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment