Leetcode 126: word ladder - a practice (IV)

May 30, 2016

Study the Java code shown in the blog:
http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/

Here is the C# code to use the same ideas in the above blog (programcreek.com)
https://gist.github.com/jianminchen/3d8e5ad6042dce7e019cf11c0b1eee22

Previous blogs on Leetcode 126: word ladder

Study Java Code,
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/126.word-ladder-ii.java

and then, write C# code, and then, improve code readability, play with styles etc. Time spent: more than 8 hours +.
the code runs ok, but need more changes:
1. https://gist.github.com/jianminchen/dc64ad0cf06220d293278f874ac07ad4

2. http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up.html
3. http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up_29.html
4. http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up_52.html

Questions and Answers:

1. How about the practice? 

The practice is with better ideas, short code.
idea 1: To track the actual ladder, we need to add a pointer that points to the previous node in the WordNode class.

For example, hit -> cog, each hop with distance 5:
hit->hot->dot->dog->cog, 
hit, prev = null, 
hot, prev = hit, 
dot, prev = hot
dog, prev = dot
cog, prev = dog
So, using BFS - breadth first search, queue, once the WordNode with "cog" is found, then, whole path can be retrieved. This is a singly linked list. 
Same applies to the path: hit->hot->lot->log->cog

idea 2: In addition, the used word can not directly removed from the dictionary. The used word is only removed when steps change.

2. C# practice vs. Java practice?
Java code - use LinkedList as queue, so Julia tried to use C# LinkedList to implement the queue as well. 
C# LinkedList API used in the practice:
line 48, line 115: AddLast()           <- queue.enqueue, force to add at the end
line 63: First()                 <- queue.Peek(), just look up the front node's value, but do not remove the node
line 64: RemoveFirst()   <- queue.Dequeue()

C# practice: 
line 101: string.ToCharArray()
line 112: new string(char[])  - constructor