Leetcode 126: word ladder II - study C++ code using BFS - Queue (Practice V)

May 30, 2016

Study the code:
http://mrsuyi.com/2016/01/31/leetcode-126/

C# code:

https://gist.github.com/jianminchen/3e99a564341995e2dd93e2fd3580aaef

Questions and Answers:

1. How is the practice? 

Julia spent more than 1 hour to work on practice.

Test case:
hit -> hot -> dot -> dog - > log
hit -> hot -> lot -> log  ->  cog

1. Line 40 - 43, add beginWord into Dictionary. The code can be extracted to one standalone function.

2. Line 52, inside while loop, HashSet, try to figure out the purpose, named: bfs_nextNodes
    same distance nodes to startWord will stay in the same HashSet.

3. Line 70, arr.ToString(), debug runtime error, the string will be "new String()". Bug is fixed, using "new string(char[])"

4. Line 84 - 87, add discussion of ladders.ContainsKey(newstring), otherwise,
    ladders[newstring].AddRange(newList) through runtime error. ladders[newstring] is null pointer.
Test case:
1. First time try, only one path is added; miss the second path (hit -> hot -> lot -> log  ->  cog)

5. line 99, Dictionary API ContainsKey, not Contains, vs. HashMap

2. What is the idea to implement the solution using your own words?

The idea is much clever. 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"}