Word Ladder I

Leave a comment

November 21, 2016 by oneOokay

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

NOTE:

  • String.valueOf(chars[])
  • str.equals(str):String之间的对比不能用==
  • for (String str : Set){}
  • str.toCharArray();

四刷word ladder BFS卡在两点:

  • String.valueOf(chars[])
  • String之间的对比不能用 “==”,应该用String.equals(String)

用一个Set来存visited,尽量不要修改input

尝试用bi-directional BFS没有成功:误解了bi-directional BFS并不是说从两端开始“同时”BFS,而是始终从beginSet进行BFS,但是根据beginSet和endSet的size来swap使得beginSet size更小。

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set wordList) {
        if (beginWord.equals(endWord)) return 1;
        if (wordList == null || wordList.size() == 0){
            return 0;
        }
        
        Set<String> visited = new HashSet<>();
        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        beginSet.add(beginWord);
        endSet.add(endWord);
        visited.add(beginWord);
        visited.add(endWord);
        int step = 1;
        while (!beginSet.isEmpty() && !endSet.isEmpty()){//注意这里必须是&&,
不能用||。当不存在路径的时候,其中的一个set会为空
            Set<String> tmpSet = new HashSet<>();//新的一个set来存下一层的words
            for (String str : beginSet){
                char[] chars = str.toCharArray();
                for(int i = 0; i < chars.length; i++){
                    char tmpc = chars[i];
                    for (char c = 'a'; c <= 'z'; c ++){
                         if (tmpc == c) continue;
                         chars[i] = c;
                         String newStr = String.valueOf(chars);
                         //这里并不需要在visited里面check
                         if (endSet.contains(newStr)){
                             return step + 1;//直接return step + 1,自己理解一下吧
                         }
                         if (!visited.contains(newStr) && 
                              wordList.contains(newStr)){                             tmpSet.add(newStr);
                              visited.add(newStr);
                             }
                     }
                     chars[i] = tmpc;//不要忘了换回来
                 }
             } 
            if (tmpSet.size() > endSet.size()){//swap beginSet和endSet
                beginSet = endSet;
                endSet = tmpSet;
            }else{
                beginSet = tmpSet;
            }
            step ++;//不要忘了step + 1;
        }
        return 0;
    }
}

 


三刷word ladder依然第一个想法是用Backtracking啊,真是没救了=。=

所以要意识到:这个是求一个最短路径的问题!而且最短路径呢都是BFS(Breadth-first search)!然后呢BFS都是用queue!

注意的技巧是:

  1. 求的并不是“需要转换几步”?也就是说求的并不是途中的“线”的数量而是“点”的数量:所以step初始值是1.
  2. 从wordList里面移除beginWord;加入endWord。
  3. 不需要nextLevel,因为当currentLevel == 0的时候,queue.size()就是nextLevel
  4. 在getNeighbors里面对wordList进行移除:可以产生不重复的neighbors也可以在主函数中防止重复访问
  5. getNeighbours返回一个Set
  6. for loop 把Set中的元素加入到queue中
  7. 最终返回为0:如果没有在while loop中返回的话,说明没有找到一条路径。

厉害的Two-end BFS 优化:两个sets:一个beginSet;一个endSet;把size较小的作为beginSet,然后对beginSet里面的单词去get neighbors。从首尾同时向对方找路径。

至于为什么这样会更快,有人贴了这个,没看太懂:

“The idea behind bidirectional search is to run two simultaneous searches—one forward from the initial state and the other backward from the goal—hoping that the two searches meet in the middle. The motivation is that b^(d/2) + b^(d/2) is much less than b^d. b is branch factor, d is depth. “

—– section 3.4.6 in Artificial Intelligence – A modern approach by Stuart Russel and Peter Norvig


Nov 2

首先Word LadderI,应该是不能用dp,因为我找不到两步之间的联系。

然后想错了,想成了用DFS和backtracking,不知道怎么DFS深入,按index来也不对。

http://bangbingsyb.blogspot.com/2014/11/leetcode-word-ladder-i-ii.html

“从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。

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

无论是求最短路径长度还是求所有最短路径,都是用BFS。

在BFS中有三个关键步骤需要实现:

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

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

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

所以总体思想是就是用BFS的方法,一个单词能够经过一步转换成在wordList中的这些所有的单词,构成了一“层”:如果这“层”中存在end word,直接返回步数;若不存在,则继续从queue中pop出来。同时一个数记录下该“层”的所有单词数,每pop出一个,数目减1.减为0的时候,说明该层结束了,step数+1,进行下一层的访问。(就像用BFS算总层数一样)

然后要注意String相关操作的技巧。

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set wordList) {
        if (beginWord == null || beginWord.length() == 0 || endWord == null 
|| endWord.length() == 0 || wordList == null || wordList.size() == 0){
            return 0;
        }
        if (beginWord.equals(endWord)){
            return 1;
        }
        Set visited = new HashSet();//一个额外的set来存已经访问过的点,避免重复访问
不选择在wordList里面移除,因为要避免更改input
        visited.add(beginWord);
        int step = 1;
        Queue queue = new LinkedList();
        queue.offer(beginWord);
        int current = 1;//这里并不需要一个next来存下一层的单词数,
因为当current变为0的时候,所有queue里面所存在的元素就都是下一层的元素,所以下一层的
单词数就是queue.size()
        while (!queue.isEmpty()){
            String s = queue.poll();
            current --;
            
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i ++){
                char tmp = chars[i];//这里要存好原本的char,在for loop结束的时候要恢复
            for (char j = 'a'; j < 'z'; j ++){
                if (tmp == j){//这里要用tmp进行对比,而不能用chars[i],因为chars[i]已经变动过了
                    continue;
                }
                chars[i] = j;
                String newStr = String.valueOf(chars);
                if (newStr.equals(endWord)){
                    return step + 1;
                }
                if(!visited.contains(newStr) && wordList.contains(newStr)){
                    queue.offer(newStr);
                    visited.add(newStr);
                }
            }
            chars[i] = tmp;//恢复chars[i]
            }
            
            if (current == 0){
                step ++;
                current = queue.size();
            }
        }
        return 0;//最终要是没有找到endWord的话说明
endWord不存在或者路径不存在,返回0
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: