Thursday, April 19, 2018

Leetcode 126: Word ladder II

April 19, 2018

Introduction


It is the hard level algorithm and I like to spend time to go over a few more ideas through Google search and Leetcode discussion panel. What I like to do is to go over more detail how to address time and memory limit exceeded problem.

I spent over 30 minutes already to go over my past practice and a few ideas, I like to go over this blog.

Algorithm practice


I like to go over the notes written in Chinese in the blog, and then rewrite some of them, make it my own.

As a programmer, most of important for me right now is to be a good thinker. I like to search the blogs and find the idea to help me think clearly. Here is the notes:

LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题,但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化?

1. 将每个单词看成图的一个节点。
2. 当单词s1 改变一个字符可以变成存在于字典的单词 s2 时,则s1与s2之间有连接。
3. 给定s1和s2,问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。


How do I go over the notes above? 

1. Google search the shortest path in the graph. 
2. How to define a graph? Every word is a node in the graph. 
3. Node s1 and node s2 have a connection -> how to define it?

Let me work on the notes in the following:

无论是求最短路径长度还是求所有最短路径,都是用BFS。在BFS中有三个关键步骤需要实现:

1. 如何找到与当前节点相邻的所有节点。
这里可以有两个策略:
(1) 遍历整个字典,将其中每个单词与当前单词比较,判断是否只差一个字符。复杂度为:n*w,n为字典中的单词数量,w为单词长度。
(2) 遍历当前单词的每个字符x,将其改变成a~z中除x外的任意一个,形成一个新的单词,在字典中判断是否存在。复杂度为:26*w,w为单词长度。
这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说,长度大多小于100,而字典中的单词数则往往是成千上万,所以策略2相对较优。

2. 如何标记一个节点已经被访问过,以避免重复访问。
可以将访问过的单词从字典中删除。

3. 一旦BFS找到目标单词,如何backtracking找回路径?



No comments:

Post a Comment