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