LeetCode 127. Word Ladder

Question

Explanation

本题用DFS做会严重超时，用BFS也要注意一下替换的方式。其实用双边BFS会更快。

Code

Solution 1: BFS

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>();
        for (String word : wordList) {
            dict.add(word);
        }

        if (wordList == null) return 0;
        if (beginWord.equals(endWord)) return 1;
        // wordList.add(beginWord);
        // wordList.add(endWord);

        HashSet<String> hash = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        hash.add(beginWord);

        int length = 1;
        while(!queue.isEmpty()) {
            length ++;
            int size = queue.size();
            for(int i=0; i<size; i++) {
                String word = queue.poll();
                for (String nextWord: getNextWords(word, dict)) {
                    if (hash.contains(nextWord)) {
                        continue;
                    }
                    if (nextWord.equals(endWord)) {
                        return length;
                    }
                    hash.add(nextWord);
                    queue.offer(nextWord);
                }
            }
        }
        return 0;
    }

    private List<String> getNextWords(String word, Set<String> wordList) {
        List<String> nextWords = new ArrayList<>();
        for (char c = 'a' ; c <'z'; c++) {
            for (int i=0; i< word.length(); i++){
                if (c == word.charAt(i)) {
                    continue;
                }
                String nextWord = replace(word, i, c);
                if (wordList.contains(nextWord)) {
                    nextWords.add(nextWord);
                }
            }
        }
        return nextWords;
    }

    private String replace(String word, int i, char c) {
        char[] chars = word.toCharArray();
        chars[i] = c;
        return new String(chars);

    }
}