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 

Leetcode 126: Word Ladder II - warm up practice (III)

May 29, 2016

 Share one tweet from profession tennis play Angelique Kerber (2016 Australian Grand Slam champion):
https://twitter.com/AngeliqueKerber/status/734019444868059136

"Everyone asks me what's next. I'm here to stay, taking it one game at a time."


 One algorithm at a time. Still work on Leetcode 126: word ladder II,

 Here is the practice version on May 28, 2016, less than 15 hours ago.


 And then, she spent over 2 hour to make changes on the code, here is the 2nd version:

https://gist.github.com/jianminchen/90075ee13a6ad0d9d59c8843d17e3a18

 And then, she continued to spend over 2+ to write the code again, here is the third version:

https://gist.github.com/jianminchen/5570fdb038f5d5d2fd2d64af09fdb643

Question and Answer:

1. What do you learn through the practice? 

Julia created three bugs: 

1. First, function call on line 59, return dist = 0. 

Because endWord, such as "cog" should be added to HashSet<string> and then use it in the function call on line 59, 

instead of original HashSet<string> wordList. 

line 144, wordList.Contains(trial), last word "cog" is not in wordList, therefore, function can not function normally. 

2. Second, function call on line 73, wordListExtended should be used instead of wordList, 

otherwise, the endWord is not in HashSet<string>, cannot find ladders. 

line 247 cannot return true when ij_word is endWord "cog": wordList.Contains(ij_word)

3. Third, in function getLadder_DFS_Backtracking  on line 204 - 271, line 219 is commented out, 

dictionary[runner] < dist, cannot be =, otherwise, ladders with distance 5 and 6 both are included. Instead of 2 list, 

there are 6 lists. 

2. What improvement does this practice make? 

2nd version:

https://gist.github.com/jianminchen/90075ee13a6ad0d9d59c8843d17e3a18

3rd version:
https://gist.github.com/jianminchen/5570fdb038f5d5d2fd2d64af09fdb643

a.  In 3rd version, remove 2nd version from line 37 - 44.

b.  In 3rd version, line 71, variable name is changed from visited to visitedHelper.

c.  In 3rd version, function findDistAndPrepareDictionary_BFS_UsingQueue, last line,

d.  line 153, return 0; in 2nd version, length is return.

e.  In 3rd version, line 106, int length - variable, can be removed, no use at all.

f.  In 3rd version, removed 2nd version nested if - line 141. 

g. In 3rd version, Tuple class is used to avoid using two queues.

Actionable items:

1. More practice, goal is to write executable code with correct result.

2. Study more solutions.

Leetcode 126: Word Ladder II - warm up practice (II)

May 29, 2016

 Share one tweet from profession tennis play Angelique Kerber (2016 Australian Grand Slam champion):
https://twitter.com/AngeliqueKerber/status/734019444868059136

"Everyone asks me what's next. I'm here to stay, taking it one game at a time."


 One algorithm at a time. Still work on Leetcode 126: word ladder II,

 Here is the practice version on May 28, 2016, less than 15 hours ago.
http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up.html

 And then, she spent over 2 hour to make changes on the code, here is the new version:

https://gist.github.com/jianminchen/90075ee13a6ad0d9d59c8843d17e3a18

 Here are the list of things she made the change:
1. line 21, class member variable is commented out. ladders.
    It is replaced by an argument in the function:
line 189 getLadders_DFS_Backtracking, 8th argument - ladderHelper

2. line 27, comment out member variable ladderHelper, pass an argument in
function getLadders_DFS_Backtracking line 189, last argument: List<string> ladderHelper

3. line 60, change function name to getLadders_DFS_Backtracking, remind myself two things:
1. it is a DFS algorithm
2. Do not forget to do backtracking

4. line 102, change function name to getLadderLengthAndDictionary_BFS. BFS stands for 
breadth first search.

5. line 203, line 204, add two more explanation variable, make code more readable.
isEndWord, 
isBeforeEndWord

6. line 220, add explanation variable, backtracking_char, helps user to understand 
the backtracking process.

7. line 221, add explanation variable replace, the char will be replaced by any one of from 'a' to 'z'.

8. line 225, 226
if(j == replace)
  continue;

Make the code more flat, no nested two if statements, only one if statement.

9. line 229, ij_word, ij prefix helps to track index i and index j.
10. line 245, line 249, line 251 3 backtracking statements.