WordLadder

WordLadder I 找最短路径首先想到用BFS去找 解法一:

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (beginWord == null || endWord == null) {
            return 0;
        } else if (beginWord.equals(endWord)) {
            return 1;
        }

        wordList.add(endWord);
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int distance = 1;

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

            for (int j = 0; j < size; j++) {
                String word = queue.poll();

                List<String> nextWords = new ArrayList<String>();
                char[] chars = word.toCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    for (int i = 0; i < chars.length; i++) {
                        char temp = chars[i];
                        chars[i] = c;
                        String nextWord = String.valueOf(chars);
                        if (nextWord.equals(endWord)) {
                            return distance + 1;
                        }

                        if (!visited.contains(nextWord) && wordList.contains(nextWord)) {
                            nextWords.add(nextWord);
                            visited.add(nextWord);
                        }

                        chars[i] = temp;
                    }
                }

                for (String nextWord: nextWords) {
                    queue.offer(nextWord);
                }
            }
            distance++;
        }

        return 0;
    }
}

解法二: search from both beginWord side and endWord side. 这个解法超过了91%的解的速度.

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (beginWord == null || endWord == null) {
            return 0;
        }

        Set<String> beginSet = new HashSet<String>();
        Set<String> endSet = new HashSet<String>();
        beginSet.add(beginWord);
        endSet.add(endWord);
        int length = 1;

        Set<String> visited = new HashSet<String>();
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                Set temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }

            Set<String> temp = new HashSet<String>();
            for (String word: beginSet) {
                char[] chars = word.toCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    for (int i = 0; i < chars.length; i++) {
                        char d = chars[i];
                        chars[i] = c;
                        String newWord = String.valueOf(chars);

                        if (endSet.contains(newWord)) {
                            return length + 1;
                        }

                        if (!visited.contains(newWord) && wordList.contains(newWord)) {
                            visited.add(newWord);
                            temp.add(newWord);
                        }
                        chars[i] = d;
                    }
                }
            }

            beginSet = temp;
            length++;
        }

        return 0;
    }
}

WordLadder II 先用bfs找到最短的word ladder, 同时用一个hash map来维护一个distance和List words之间的关系。然后用dfs去遍历出所有可能的解。在dfs的过程中，在把一个word放入到中间结果前，先check一下，这个word能不能从上一个word那里convert过来的。

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (beginWord == null || endWord == null) {
            return result;
        }

        Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        int length = bfs(beginWord, endWord, wordList, map);
        if (length == 0) {
            return result;
        }

        List<String> list = new ArrayList<String>();
        list.add(endWord);
        dfs(result, list, length - 1, map, endWord);
        return result;
    }

    private void dfs(List<List<String>> result, List<String> list, int length, Map<Integer, List<String>> map, String prev) {
        if (length == 0) {
            result.add(new ArrayList<String>(list));
            return;
        }

        for (String word: map.get(length)) {
            if (canConvertFromPrev(word, prev)) {
                list.add(0, word);
                dfs(result, list, length - 1, map, word);
                list.remove(0);
            }
        }
    }

    private boolean canConvertFromPrev(String current, String prev) {
        int diff = 0;
        for (int i = 0; i < current.length(); i++) {
            char c1 = current.charAt(i);
            char c2 = prev.charAt(i);

            if (c1 != c2) {
                diff++;
            }
        }

        return diff == 1;
    }

    private int bfs(String beginWord, String endWord, Set<String> wordList, Map<Integer, List<String>> map) {
        wordList.add(endWord);
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        queue.offer(beginWord);
        visited.add(beginWord);
        map.put(1, new ArrayList<String>());
        map.get(1).add(beginWord);
        int length = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                if (word.equals(endWord)) {
                    return length;
                }

                char[] chars = word.toCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    for (int j = 0; j < word.length(); j++) {
                        char temp = chars[j];
                        chars[j] = c;
                        String newWord = String.valueOf(chars);
                        if (!visited.contains(newWord) && wordList.contains(newWord)) {
                            visited.add(newWord);
                            queue.offer(newWord);
                            if (!map.containsKey(length + 1)) {
                                map.put(length + 1, new ArrayList<String>());
                            }
                            map.get(length + 1).add(newWord);
                        }
                        chars[j] = temp;
                    }
                }
            }

            length++;
        }

        return 0;
    }
}