2015年6月10日星期三

[LeetCode] Word Ladder

Problem:

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, 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.

Java Code:

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        dict.remove(start);
        int length = 1;
        while (queue.peek() != null) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String temp = queue.poll();
                for (char c = 'a'; c <= 'z'; c++) {
                    for (int j = 0; j < temp.length(); j++) {
                        if (c == temp.charAt(j)) {
                            continue;
                        }
                        char[] chars = temp.toCharArray();
                        chars[j] = c;
                        String cur = new String(chars);
                        if (cur.equals(end)) {
                            return length + 1;
                        }
                        if (dict.contains(cur)) {
                            queue.offer(cur);
                            dict.remove(cur);
                        }
                    }
                }
            }
            length++;
        }
        return 0;
    }
}

没有评论:

发表评论