Word Ladder, Leetcode 解题笔记

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

Only one letter can be changed at a time
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.

以后遇到求最短路径首先要考虑BFS。对于这道题,每次对start替换一个字符,从左到右,从a到z。对于每次变换后的字符串,检查是否在dict中,如果在,则在distance上加一,并继续比较下一位,直到与end一致时返回distance数。
BFS常用的方法是利用一个Queue,类似二叉树的行遍历。这道题因为既要保存string,又要保存distance,所以可以用两个Queue来分别保存。
因为是BFS,所以第一次找到end时就一定是最短的distance。

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        LinkedList<String> wordQ = new LinkedList<String>();
        LinkedList<Integer> distanceQ = new LinkedList<Integer>();
        
        wordQ.add(start);
        distanceQ.add(1);
        while(wordQ.size() != 0){
            String curStr = wordQ.poll();
            int curDis = distanceQ.poll();
            
            if(curStr.equals(end)){
                return curDis;
            }
            
            for(int i = 0; i < curStr.length(); i++){
                char[] charStr = curStr.toCharArray();
                for(char j = 'a'; j < 'z'; j++){
                    charStr[i] = j;
                    String transform = new String(charStr);
                    if(dict.contains(transform)){
                        wordQ.add(transform);
                        distanceQ.add(curDis+1);
                        dict.remove(transform);
                    }
                }
            }
        }
        return 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