1. Description

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:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

2. Example

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

3. Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LeetCode0127 {
    class Node {
        String str;
        int level;
        Node parent;

        public Node(String str, int level, Node parent) {
            this.str = str;
            this.level = level;
            this.parent = parent;
        }
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0) {
            return 0;
        }

        Queue<Node> queue = new LinkedList<Node>();
        queue.add(new Node(beginWord, 1, null));

        HashSet<String> visited = new HashSet<String>();
        HashSet<String> unvisited = new HashSet<String>();
        unvisited.addAll(wordList);

        int preLevel = 0;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (endWord.equals(node.str)) {
                Node p = node;
                return p.level;
            }

            if (preLevel < node.level) {
                preLevel = node.level;
                unvisited.removeAll(visited);
            }

            char[] arr = node.str.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                char c = arr[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    arr[i] = j;
                    String newStr = new String(arr);
                    if (!unvisited.contains(newStr)) {
                        continue;
                    }
                    visited.add(newStr);
                    Node newNode = new Node(newStr, node.level + 1, node);
                    queue.offer(newNode);
                }
                arr[i] = c;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        LeetCode0127 leetcode = new LeetCode0127();
        List<String> wordList = new ArrayList<String>(
                Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        System.out.println(leetcode.ladderLength("hit", "cog", wordList));
    }
}