Monday, May 30, 2016

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"}

No comments:

Post a Comment