Created
April 26, 2016 19:33
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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