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. 
   

Algorithm night (3)

January 21, 2016

Find 10 challenging algorithms questions, and then go over them one by one. It is fun, and also good learning experience.

She wishes that she could have more than 100 algorithm night, reviewed 1000 algorithms already, and each time, just so relax to go over different ideas how to solve them, by reading, and by good hints and teaching through blogs. At that time, she will be good thinker about algorithms. Wishful thinking, get back to reality (5 algorithms, 2 hours, a lot of headache, and could not figure out what is brute force solution.), work on 3rd algorithm night.

Be humble, be stupid, and learn from mistakes.

1. Leetcode 295: Find medium from data stream 

https://segmentfault.com/a/1190000003709954
https://gist.github.com/jianminchen/31572a64b2af48e3ccce


http://buttercola.blogspot.ca/2015/12/leetcode-find-median-from-data-stream.html


Julia, read Java priorityQueue class and get some ideas about the class design:
http://www.programcreek.com/2009/02/using-the-priorityqueue-class-example/

http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue

understand priority queue first, read the lecture notes:
http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf

2.  min stack
http://buttercola.blogspot.ca/2015/11/zenefits-mini-stack.html

3. 写一个函数float sumPossibility(int dice, int target)，就是投dice个骰子，求最后和为target的概率。因为总共的可能性是6^dice，所以其实就是combination sum，求dice个骰子有多少种组合，使其和为target。先用brute force的dfs来一个O(6^dice)指数复杂度的，然后要求优化，用dp，最后结束代码写的是两者结合的memorized search吧，

https://gist.github.com/diegozeng/6c964f623bbeaa716526

http://www.labnol.org/internet/github-gist-tutorial/28499/

4. Possible triangle
http://www.geeksforgeeks.org/find-number-of-triangles-possible/

http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers

Argue about how to reduce time complexity from O(N^3) to O(N^2), how exactly i, j, k three variable, k is only from 0 to n-1 once for each i, nothing to do with j. So, it is time for i - from 1 to N, and time for j from 1 to N two loops, and then for i - N, and k from 1 to N ( skip j - big point! Cannot figure out easily. )

5.  Top K int in a large stream (This can be done in O(n))
http://stackoverflow.com/questions/185697/the-most-efficient-way-to-find-top-k-frequent-words-in-a-big-word-sequence

6. Leetcode solutions - blog reading
Just read as many solution and see if there are something new to write down here:

http://www.cnblogs.com/grandyang/p/4606334.html  ( No. 1 - No. 280)

Review Leetcode questions 1 - 20 (January 24, 2016)

So, here are some notes about DFS - backtracking problem solving:

1. DFS vs BFS, DFS usually involves backtracking as well. So, remember backtracking.
2. How to design the DFS function?
    A. return result - one of arguments:
   IList<string> res
    is a good idea, also, it can be member variable of class Solution.
    B. Convert a char to integer '1' -> 1
         quickest way is c - '0'
    C. Backtracking is the key to ensure the bug free
    D. Java, C# using stringBuilder to construct string, append

Review solutions:
http://codesniper.blogspot.ca/2015/03/sticky-post-all-of-my-published.html

Java solution:  Leetcode 1 - 120

Algorithm night (2): 10 questions to read

January 20, 2016

Plan to spend 2 hours (9pm - 12pm) to read 10 blogs about algorithms, each blog 10 minutes.

1.    Leetcode: Coin Change 
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
Think about recursive function solution first, and then DP solution to remove redundant calculation

http://blog.csdn.net/kenden23/article/details/17636599
http://buttercola.blogspot.ca/2016/01/leetcode-coin-change.html

2.    Leetcode: Maximum product of word lengths 

https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/

http://buttercola.blogspot.ca/2016/01/leetcode-maximum-product-of-word-lengths.html

Brute force analysis, bit manipulation - encode string using integer, and then, optimize the algorithm - instead of two strings' comparison, using two integer bit manipulation - And operator - clever solution. 

3.   Leetcode questions: Power of 2 / Power of 3 

 http://www.cnblogs.com/grandyang/p/4623394.html
 Power of 3
http://my.oschina.net/Tsybius2014/blog/601048

  http://buttercola.blogspot.ca/2016/01/leetcode-power-of-three.html

4.    Leetcode 325: Maximum size subarray sum to K (Level: easy)

https://asanchina.wordpress.com/2016/01/05/325-maximum-size-subarray-sum-equals-k/

http://buttercola.blogspot.ca/2016/01/leetcode-maximum-size-subarray-sum.html

January 21, 2016

5.    BFS - algorithm 
http://www.geeksforgeeks.org/find-number-of-islands/
Read the blog, understand the algorithm. Rate: 10

http://www.jiuzhang.com/solutions/find-the-connected-component-in-the-undirected-graph/

http://algobox.org/number-of-connected-components-in-an-undirected-graph/

http://buttercola.blogspot.ca/2016/01/leetcode-number-of-connected-components.html

6.    Sparse Matrix Multiplication

http://www.cs.cmu.edu/~scandal/cacm/node9.html
https://leetcode.com/discuss/71912/easiest-java-solution

http://buttercola.blogspot.ca/2016/01/leetcode-sparse-matrix-multiplication.html

7.    Leetcode 310: Minimum Height Trees

https://leetcode.com/problems/minimum-height-trees/#
read the blog:
http://bookshadow.com/weblog/2015/11/26/leetcode-minimum-height-trees/
https://leetcode.com/discuss/71656/c-solution-o-n-time-o-n-space
http://likemyblogger.blogspot.ca/2015/11/leetcode-310-minimum-height-trees.html

http://buttercola.blogspot.ca/2016/01/leetcode-minimum-height-trees.html

8.  Leetcode: Remove duplicate letters

http://bookshadow.com/weblog/2015/12/09/leetcode-remove-duplicate-letters/
3 solutions are discussed in the following blog:
https://www.hrwhisper.me/leetcode-remove-duplicate-letters/

https://leetcode.com/discuss/73777/easy-to-understand-iterative-java-solution

http://buttercola.blogspot.ca/2016/01/leetcode-remove-duplicate-letters.html

9.   Leetcode: Longest increasing subsequence

http://blog.csdn.net/kenden23/article/details/17632821

spend 10 minutes to read the blog:
http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73075
http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
Previous blog:
http://juliachencoding.blogspot.ca/2015/06/dynamic-programming-longest-increasing.html

Write some C# code for this algorithm later.

http://buttercola.blogspot.ca/2015/12/leetcode-longest-increasing-subsequence.html

NLogn solution, better than DP solution, Recursive solution
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Set Goals:
1. Know how to solve it using recursive solution first;
2. And then, understand DP solution, how to build the formula, avoid duplication;
3. And then, know where to find optimal solution here, O(nlogn),

10. Leetcode: Binary Tree Longest Consecutive Sequence

Excellent chance to practice recursive function

https://segmentfault.com/a/1190000003957798

http://buttercola.blogspot.ca/2015/12/blog-post.html

Leetcode questions 20: Valid Parentheses

January 20, 2016 

Leetcode 20: Valid parentheses

http://blog.csdn.net/fightforyourdream/article/details/13011825

Julia’s C# code:

https://github.com/jianminchen/Leetcode_C-/blob/master/20ValidParentheses.cs

January 20, 2016

https://github.com/jianminchen/Leetcode_C-/blob/master/20ValidParentheses_B.cs 

favorite blogs to read: January 20, 2016

Great time to go over different ideas to implement the algorithm, using Map in C++, Hashmap, and see so many talents through those code - 

http://bangbingsyb.blogspot.ca/2014/11/leetcode-valid-parentheses.html

http://www.acmerblog.com/leetcode-solution-valid-parentheses-6316.html

http://blog.csdn.net/foreverling/article/details/49685177?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io

http://segmentfault.com/a/1190000003481208

http://harrifeng.github.io/algo/leetcode/valid-parentheses.html

http://www.jiuzhang.com/solutions/valid-parentheses/

So, ready to review more about parentheses:

Leetcode 32: longest valid parentheses -

http://codeganker.blogspot.ca/2014/03/longest-valid-parentheses-leetcode.html

Julia’s blog on this question:
Leetcode question 22: Generate Parentheses
https://github.com/jianminchen/Leetcode_C-/blob/master/GenerateParentheses_No22.cs

Leetcode question 32:
32 Longest Valid Parentheses

http://codeganker.blogspot.ca/2014/03/longest-valid-parentheses-leetcode.html

http://bangbingsyb.blogspot.ca/2014/11/leetcode-longest-valid-parentheses.html

http://blog.csdn.net/worldwindjp/article/details/39460161

http://shanjiaxin.blogspot.ca/2014/04/longest-valid-parentheses-leetcode.html

C# code:
https://github.com/jianminchen/Leetcode_C-/blob/master/32LongestValidParentheses.cs

Book Reading: C# book Effective C#

January 20, 2016

Julia came cross this C# book:

Effective C# (Covers C# 4.0): 50 Specific Ways to Improve Your C#

http://www.amazon.com/Effective-Covers-4-0-Specific-Development/dp/0321658701

Read item 2:

Item 2: Prefer readonly to const

Need to spend time to read very well-written articles about C#, and enjoy learning.

Try to find more books about C# to improve algorithm writing - code, design and more. 

Leetcode 317: Shortest distance from all buildings (part 2)

January 19, 2016

Problem statement:

 You want to build a house on an empty land which reaches all buildings in the shortest amount

  of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2,

  where:

        Each 0 marks an empty land which you can pass by freely.

        Each 1 marks a building which you cannot pass through.

        Each 2 marks an obstacle which you cannot pass through.

        For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

    1 - 0 - 2 - 0 - 1

    |   |   |   |   |

    0 - 0 - 0 - 0 - 0

    |   |   |   |   |

    0 - 0 - 1 - 0 - 0

     *

     * The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is

     * minimal. So return 7.

     *

Practice using C#

Julia chose this Java code implementation to study first, and then she wrote one using C#.

She spent more than 2 hours from 9pm - 11pm to practice.

Highlights of changes

1. Julia likes the idea of "express the intent", so she added a new function called getNoOfBuildings().

So,  here is the version to fix the bug.

Rewrite the fill function, make the function do one task:

public void fill(int origX, int origY, int x, int y, int curDistance, int[][] dist, int[][] reach,int[][] grid, bool[][] visited, Queue<Node> queue)

The above function is too complicated, Julia create a few bugs in the function. More than 8 arguments - too many!

Here is the version after some work on function design 

- get rid of too many arguments

- function much more easy to read, understand

- less error-prone

- function to do one task only

C# code is here.

Another version is here.

Lessons Julia learned through debugging:

1. using ref or not in C# language - does not matter

2. function design - simple, is important to review, avoid bugs

3. Queue is used for BFS, and when the node is added to queue. please also log the distance, and use it for next round. - Main bug - calculation, since each node has different distance to the building node.

More about BFS

1. BFS - how to think about the algorithm?

Tips: Try to start from simple things, like count how many building, empty lands, obstacles; then, figure out which one is meaningful to work with first.

3 choices - buildings, empty land, obstacle. Choose one and see if you can  make progress

buildings - very good. Do some simple task, put all buildings in a List data structure, easy to iterate.

empty land - kind of hard to do BFS - the question is to ask a node to all building distance sum - not sum - but the minimum of sum.

So, start from each building to do BFS

2. BFS - how to design a BFS function?

So many bugs in the first 2-3 hours coding, it takes 30 minutes to understand other people's idea and code.

Go through bugs one by one later. (To be continued)

3. Encourage herself to work on BFS algorithms in the future: 

Some facts:

1. Julia could not figure out how to handle this BFS problem on January 19, 2016, she has to read other people's solution first, and also analysis, and then, start to work on coding.

2. BFS  - Ask questions:

start from where - how many of them - what order to do BFS? order matter or not?

3. Julia could not finish the BFS algorithm writing in less than 30 minutes. A lot of bugs, confusion with BFS function design, and edge case handling.

4. Past experience on BFS

Julia is still working on BFS algorithms, and like to get more experience if possible. Here is another BFS practice she did in June 2015. More reading about Leetcode 317, click here. BFS algorithm review is here.

5. How to make BFS algorithm design experience fun, memorable?

- Have more discussion on the blog. Welcome comments.

Algorithms night (1)

January 17, 2016

Spent Sunday evening (8pm - 12pm) to work on algorithms questions. Just read the blogs, and get some ideas how to solve the problems. 

1. String parenthesis to see if all of them are pair correctly

Leetcode 20: valid parentheses

http://buttercola.blogspot.ca/2014/07/leetcode-valid-parentheses.html

http://www.shuatiblog.com/blog/2014/05/09/Valid-Parentheses/

2. Count the number of palindromes in  a string

 (January 28, 2016)
    Come back to write down ideas:
    1. First of all, do not count duplicate.
    2. Brute force solution:
 any substring of O(N^2) substrings to see if it is a palindrome;
 Add the substring of palindrome to a hashset if it is not in the hashset.
  And return the length of hashset
    3. Use recursive solution - using subproblem to solve. Cannot filter out duplicate - not good
    4. Better solution - use center point of string - 2n + 1, and then, go over each one, add all palindromes substring.

  Requirement: write a C# code in 10 minutes for the solution, using brute force one.

  https://github.com/jianminchen/AlgorithmsPractice/blob/master/NumberOfDistinctPalindromes.cs

3. Write a function to detect if the string has the unique character. 

Read the blog: 

http://stackoverflow.com/questions/19484406/detecting-if-a-string-has-unique-characters-comparing-my-solution-to-cracking

this blog provides good answers for the question of unique character:

Notice that this method doesn't allocate an array of booleans. Instead, it opts for a clever trick. Since there are only 26 different characters possible and there are 32 bits in an int, the solution creates an int variable where each bit of the variable corresponds to one of the characters in the string. Instead of reading and writing an array, the solution reads and writes the bits of the number.

Julia's comment: first blog about bit manipulation - surprising, after the reading, it is much easy to understand the code: 
Two bit operation: 
1<< val 
 |=  

It is always helpful to understand the 

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?
        return false;
    }
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

http://javahungry.blogspot.com/2014/11/string-has-all-unique-characters-java-example.html

4. A single linked list, delete a node but only know the node pointer which needs to be deleted. How to do it?

http://www.geeksforgeeks.org/in-a-linked-list-given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/

5. Leetcode/ Lintcode: binary tree maximum path sum

Leetcode 124: binary tree maximum path sum
http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-maximum-path-sum.html


Review the blog:
http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

6. Minimum height of a binary search tree

http://www.programcreek.com/2013/02/leetcode-minimum-depth-of-binary-tree-java/

string function - strStr - BoyerMoore algorithm - needle in hay

January 5, 2016

Read the Java code on the following website:
http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

Write a C# version, and check in github, and see if it will help to memorize the algorithm.  

Read the webpage: (well written! now Julia knows two rules: bad character rule, the good suffix rule)
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html


previous study:

http://juliachencoding.blogspot.ca/2015/06/leetcode-strstr-function.html

http://juliachencoding.blogspot.ca/search/label/string%20functions%20review