首页 > 搜索 > BFS搜索 > Word Ladder-LeetCode[BFS]
2014
08-26

Word Ladder-LeetCode[BFS]

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

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

For example,

Given:
start = "hit"
end = "cog"
dict = ["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.

题目大意:给一个字符串的集合dict ,和一个开始字符串start和结束字符串end。每次只能对 start字符串修改一个字符,并且修改过的字符串必须在dict里面。求出从start到end需要的最少的修改的次数。

分析:可以把这些单词之间的联系想象成一个无向图,如果一个单词修改一个字符可以转换成另外一个单词,则可以认为这两个单词之间有路径存在。当然,所有路径的权重都为1。这个一个典型的BFS搜索问题,BFS总是可以保证找到的路径的最短的。

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {

        if (dict.size() == 0)  
            return 0; 
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.push(new Node(start, 1));
        while(!queue.isEmpty()){
        	Node top = queue.pop();
            if(top.word.equals(end)){
                return top.len;
            }

            for(int i=0; i<top.word.length(); i++){
                char[] currCharArr = top.word.toCharArray();
                for(char c='a'; c<='z'; c++){
                    currCharArr[i] = c;

                    String newWord = new String(currCharArr);
                    if(dict.contains(newWord)){
                        queue.add(new Node(newWord, top.len+1));
                        dict.remove(newWord);//删除掉遍历过的单词
                    }
                }
            }
        }

        return 0;
    }
    static class Node{
    	String word; 
    	int len;//当前遍历的层数
    	public Node(String w,int l){
    		word = w;
    		len = l;
    	}
    }
}

  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”