Created
May 12, 2016 20:56
-
-
Save jianminchen/872bf70039fa8c61ff208b34a591c8ec to your computer and use it in GitHub Desktop.
Leetcode 17: phone number - using DFS, stack warmup practice on May 12, 2016
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_usingDFS_Stack | |
{ | |
/* | |
* 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 | |
{ | |
public class Node | |
{ | |
public string phoneStr; | |
public int length; | |
} | |
static void Main(string[] args) | |
{ | |
IList<string> list = letterCombination("234"); | |
// 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" }; | |
buildResult_usingDFS_stack(list, keyboard, digits); // think about design here | |
return list; | |
} | |
/* | |
* Julia's practice on May 12, 2016 | |
* bfs和dfs都要求写。问时间复杂度是多少,各自的优缺点是啥。 | |
空间 =>构建过程中bfs比较耗内存,因为要保存一堆中间状态的string;dfs则相对少用些内存。 | |
时间 => 算清楚string+string和stringbuilder构建新的string时间复杂度有啥区别。 | |
* | |
*/ | |
private static void buildResult_usingDFS_stack( | |
IList<string> list, | |
string[] keyboard, | |
string digits | |
) // test case: "23", index value 0 and 1 | |
{ | |
// need to complete the task using Queue | |
if (digits == null || digits.Length == 0) | |
return; | |
Stack<Node> stack = new Stack<Node>(); | |
foreach (char c in keyboard[digits[0] - '0']) | |
{ | |
Node node = new Node(); | |
node.length = 1; | |
node.phoneStr = c.ToString(); | |
stack.Push(node); | |
} | |
while (stack.Count > 0) | |
{ | |
Node node = (Node)stack.Pop(); | |
string s1 = node.phoneStr; | |
int len = node.length; | |
if (digits.Length == len) | |
{ | |
list.Add(s1); | |
} | |
else | |
{ | |
foreach (char c in keyboard[digits[len] - '0']) | |
{ | |
Node newNode = new Node(); | |
newNode.length = len + 1; | |
newNode.phoneStr = s1 + c.ToString(); | |
stack.Push(newNode); | |
} | |
} | |
} | |
return; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment