Leetcode 126: word ladder II - using BFS - Queue, Set Paths (Practice VI)

May 30, 2016

Study the blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-study-c.html

And continue to write C# solution - focus on coding, design ideas.
1. First practice, with a bug on just after line 111 - missing to add tmpList to newList.
https://gist.github.com/jianminchen/9e45848c86ebaaa8f0bc0d881cfd1ad5

2. Fix the bug and pass the test case, add line 112:
https://gist.github.com/jianminchen/e3466a9f1319f62f869aa53487c05536

Questions and Answers:

1. How is the practice?

Here are some sharing:
1. Write down the comment about the idea to solve the problem, from line 23 - line 58

Good idea is to solve 50% of problem. Repeat the idea in the following:

Explain the idea using the test case:

dot -> dog           hit->hot ->                    -> cog                               lot -> log           so, the queue process is (breadth first search)           first  layer:        hit           second layer:   hot           third  layer:      dot, lot           forth  layer:      dog, log           fifth  layer:        cog                      build ladders step by step, from startWord to current.                       Dictionary<string, List<List<string>>> ladders                      each string will be the key in ladders           hit -> hit           hot -> one list, {"hit", "hot"}           dot -> one list, {"hit", "hot", "dot"}           lot -> one list, {"hit", "hot", "lot"}           dog -> one list, {"hit", "hot", "dot", "dog"}           log -> one list, {"hit", "hot", "lot", "log"}           cog -> two lists,                            {"hit", "hot", "dot", "dog", "cog"}                            {"hit", "hot", "lot", "log", "cog"} 2. Some highlights? First of all, first writing is wrong. There are 5 levels, 4 loops and then one if, Julia got confused the position of code. So, marks are added in the comment just after the loop - start statement and also close }. Work on indentation - Better to write down your own marks.  line 75   // level 1, while loop      line 88   // level 2, for loop           line 93   // level 3, for loop                   line 97   // level 4, for loop                       line 104  // level 5, if statement                       line 121 //  end of level 5, }                   line 122 // end of level 4, }           line 125 // end of level 3, - end for loop for hop string length     line 128   // end of level 2, - processing - all nodes in the same distance in the queue line 139  // level 1 - processing queue - queue.Count > 0 line 95, char variable name: char backtracking_char, just friendly remind to do backtracking later on line 124. line 102, string variable name change: newstring -> nextHop, hopefully the current one is more meaningful. 3. Actionable items? Write again a few times, try to finish coding in 30 minutes, and write down issues not resolved. Coding is like sports, just do it!  4. More to share about the algorithm? Share one graph to illustrate the graph problem of word ladder: 5. A lot of people complained the problem is too tough. Julia, you miss the most important things in the design? Time out is a big issue. And also, we need to discuss how to avoid a cycle in the list; multiple paths can be found from start word to end word. Challenge 1:  The visited word must be removed sometime to avoid a cycle; Challenge 2:  When to remove visited words from dictionary properly? Same distance, one word can repeat multiple times. Sure, let us talk about it! on line 84, inside the while loop, Hashset<string> nextHops_BFS are defined. We need to examine this Hashset: on line 120, nextHop is added one by one to the HashSet, but no action is taken on the HashSet. Lazy processing here! Until all nodes in the current layer are processed, dequeue from the queue. From line 133 - 137, add next layer hops into the queue, where to find the nodes - nextHops_BFS . Remove the words from wordList just before adding to the queue. Put line 135 just after line 120, and see what is difference. The program will generate no output for test case:                               dot -> dog           hit->hot ->                    -> cog                               lot ->  log log word's next layer is cog, and dog word's next layer is cog as well. Both routes have same word, terminate word. cog can not be removed from wordDist Hashset until two routes are processed both. Actually, the graph should look likes the following:                                     dot -> dog -> cog           hit->hot ->                                                  lot -> log -> cog  In fifth layer, cog word shows up on line 102 twice: line 102 if (wordList.Contains(nextHop)) So, 2 lists can be added with the same word "cog" as last one. It is important to keep wordList untouched until the whole layer is processed, then, remove words in HashSet nextHops_BFS from wordList.  Rules to obey in the design:1. The same word does not repeat twice in the same list. For example, hit->hot->lot->log->lot-log..., it may go on forever.  2. One word does not show up in more than one list, except start word and end word. For example, test case, hit, cog are only exceptions.  Not True. "hot" shows up in two lists.  3. Words in the distance n should not be any word in distance 0 to n-1.                               dot -> dog           hit->hot ->                    -> cog                               lot ->  log So, when dog or log are processed in the queue, all words less than 4, hit, hot, dot, lot should be removed from HashSet wordList.  Need to go through those cases one by one.  Actionable items: Read the blog and then implement the solutions as well. http://www.cnblogs.com/shawnhue/archive/2013/06/05/leetcode_126.html