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.