Leetcode 17: Letter Combinations of a phone number (DFS)

January 24, 2016
 
17 Letter Combinations of a phone number (DFS)

Julia likes to focus on basic things about algorithms, she tries to focus on recursive function design, BFS, DFS, backtracking. Here is her favorite DFS algorithm, she tries to build more fun memory about DFS algorithm, every time she works on DFS algorithm, she is so happy and eager to share her 2 cents, learned from Leetcode blogs - all her favorite blogs.

http://www.cnblogs.com/grandyang/p/4452220.html
Analysis from the above blog:
这道题让我们求电话号码的字母组合，即数字2到9中每个数字可以代表若干个字母，然后给一串数字，求出所有可能的组合，相类似的题目有 Path Sum II 二叉树路径之和之二，Subsets II 子集合之二，Permutations 全排列，Permutations II 全排列之二，Combinations 组合项， Combination Sum 组合之和和 Combination Sum II 组合之和之二等等。我们用递归Recursion来解，我们需要建立一个字典，用来保存每个数字所代表的字符串，然后我们还需要一个变量level，记录当前生成的字符串的字符个数，实现套路和上述那些题十分类似，

Her practice is too weak in 2015.
https://github.com/jianminchen/Leetcode_C-/blob/master/LetterCombinationOfAPhoneNumber.cs

Missing in the last practice:
1. Use iterative solution, but lack of analysis - (comment area, hard to review)
2. Should focus on DFS solution, basic things.

New practice in January 2016:
1. using recursive to solve the problem, it is fast and quick way to solve it in 10 minutes.
2. Only need to write a few lines of code.
3. Need to design recursive function.
4. Need to do backtracking,
5, Need to do char, string, int a few types, and also do type conversion.

Julia's practice, it took her 27 minutes to write down, compile, and have some comment written.
https://github.com/jianminchen/Leetcode_C-/blob/master/17LetterCombinationOfAPhoneNUmber_DFS.cs

January 24, Read more blogs on this question:

和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母，并加入当前combination中传到下一层递归。
Iterative solution: 这里需要克隆多份之前的解集。
http://bangbingsyb.blogspot.ca/2014/11/leetcode-letter-combinations-of-phone.html

Java, using hashmap - Good idea
http://blog.welkinlan.com/2015/10/25/letter-combinations-of-a-phone-number-leetcode-java/

终于出现我最不擅长的递归题了，这道题是经典递归题，标准DFS解法，应作为模板牢牢记住。
http://simpleandstupid.com/2014/10/16/letter-combinations-of-a-phone-number-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/

So, Julia is not good at recursive function design as well. So, she likes to search a blog and find the most important tip she can grasp in next 20 minutes.

Array initiliazation can be in one line instead of more than 8 lines
http://yucoding.blogspot.ca/2013/01/leetcode-question-42-letter.html

DFS, backtracking is clear in the code.
http://rleetcode.blogspot.ca/2014/02/letter-combinations-of-phone-number-java.html

Java code, member of class - hashmap - static - first time read static - declare variables sharing static in statement. (missing backtracking? or does not matter)
https://github.com/rffffffff007/leetcode/blob/master/Letter%20Combinations%20of%20a%20Phone%20Number.java

very well written,
http://codesniper.blogspot.ca/2015/01/17-letter-combinations-of-phone-number.html

using vector instead of hashmap
http://yumei165.blogspot.ca/2013/04/letter-combinations-of-phone-number-c.html

Good analysis - read the analysis in the following blog -

• 这个是一个结果是排列组合的问题,一个类似的问题就是小组赛N个队, 相互之间的比赛 列表. 这种问题就是回溯法
• 回溯法最重要的就是要"先加再减" (Julia's comment -> backtracking ) 
• 回溯法函数参数的设计是把结果当成参数(此处是用参数引用), 返回值返回一个void. 这样容易设计递归.
• java的做法会比c++看起来麻烦一点, 而且java是无法做到真的const String数组

http://harrifeng.github.io/algo/leetcode/letter-combinations-of-a-phone-number.html

九章算法
http://www.jiuzhang.com//solutions/letter-combinations-of-a-phone-number/

Analysis from the following blog:
Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 
http://buttercola.blogspot.ca/2014/09/leetcode-letter-combinations-of-phone.html

use this one as my example to write a good solution. Good style!
https://segmentfault.com/a/1190000003766442

Excellent code style.
http://shanjiaxin.blogspot.ca/2014/02/letter-combinations-of-phone-number.html

So, put together something for DFS /backtracking algorithm - favorite tips:
1. DFS, do not forget backtracking, using Chinese words, "先加再减". 
2. Recursive function design:
    Return result C#: IList<string>, 
    put it as input argument or member variable of class Solution 
3. Remember a tip to convert a char to int, very basic convert using this: 
    Char c (no one can remember the ascii value of '0', but use type conversion c-'0', char to int; in other words, compare to relative char, get the value by type conversion automatically).
    c - '0' 

4. dictionary declaration, common and easy way is to declare one dimension array:

    String[] table = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

5. using C# or Java, string class is not good, using StringBuilder class instead. 

6. Remember one or two DFS algorithms, use them to relax and help to figure out design issue, difficulty level of DFS problem solving - honestly, it is easy and quick solution, less time-consuming compared to an iterative solution, more time-consuming DP with memorization solution.