Version I - BFS

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> words = new HashSet<>(wordList);

        Queue<String> queue = new LinkedList<>();

        int level = 0;
        queue.offer(beginWord);

        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();

            for (int i = 0; i < size; ++i) {
                String word = queue.poll();
                if (word.equals(endWord)) return level;
                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; ++j) {
                    char c = chars[j];
                    for (char k = 'a'; k <= 'z'; ++k) {
                        chars[j] = k;
                        if (words.contains(String.valueOf(chars))) {
                            queue.offer(String.valueOf(chars));
                            words.remove(String.valueOf(chars));
                        } 
                    }
                    chars[j] = c;
                }

            }

        }

        return 0;
    }
}

Version II - two-end BFS

dont' forget the case when end word is not in the word list

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> words = new HashSet<>(wordList);

        if (!words.contains(endWord)) return 0;

        HashSet<String> beginSet = new HashSet<>();
        HashSet<String> endSet = new HashSet<>();

        beginSet.add(beginWord);
        endSet.add(endWord);

        int level = 1;

        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                HashSet<String> set = beginSet;
                beginSet = endSet;
                endSet = set;
            }

            HashSet<String> tmpSet = new HashSet<>();

            for (String word : beginSet) {
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; ++i) {
                    char c = chars[i];
                    for (char j = 'a'; j <= 'z'; ++j) {
                        chars[i] = j;
                        String str = String.valueOf(chars);
                        if (endSet.contains(str)) {
                            return level + 1;
                        }
                        if (words.contains(str)) {
                            words.remove(str);
                            tmpSet.add(str);
                        }
                    }
                    chars[i] = c;
                }
            }

            level++;
            beginSet = tmpSet;
        }

        return 0;
    }
}

results matching ""

    No results matching ""