Leetcode 17: Phone Number - Practice using DFS/ Stack and BFS/ Queue

May 12, 2016

 Write two more practice using Queue/ BFS and DFS/ stack on this leetcode question:

Using Queue/ BFS
https://gist.github.com/jianminchen/5691a3488a2ef4f0660194502ae15f68

Using Stack/ DFS
https://gist.github.com/jianminchen/872bf70039fa8c61ff208b34a591c8ec

Previous blogs about practice:

April 21, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/04/window-sum.html

January 24, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/01/leetcode-17-letter-combinations-of.html


Question and Answer:

1. What is the difference using Queue and Stack on space usage?

For example, using Queue/ BFS, source code line:

Line 31: IList<string> list = letterCombination("234"); // test result: "abc", "def", so 3x3 = 9 cases. If the string is "2345678", 7 digits string, then, when first string is added to the list, on line 86, the queue's count is around 3^7 = 9 * 9 * 9 * 3, more than 2000 records in the queue. However, using Stack/ DFS, source code line 31, the string is "2345678", when the first phone number is added to the list, the stack size is around 3*7 = 20, around 20 records in the stack. So, it takes more space to use queue/ BFS on this problem solving, not efficient on space usage.

2. Please look into string, stringBuilder on this problem solving.
Read more blogs on this discussion: