### 描述​

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

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

### 单队列​

// Word Ladder// 时间复杂度O(n)，空间复杂度O(n)public class Solution {    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {        Queue<State> q = new LinkedList<>();        HashSet<State> visited = new HashSet<>(); // 判重        final Function<State, Boolean> stateIsValid = (State s) ->                wordList.contains(s.word) || s.word.equals(endWord);        final Function<State, Boolean> stateIsTarget = (State s) ->                s.word.equals(endWord);        final Function<State, HashSet<State> > stateExtend = (State s) -> {            HashSet<State> result = new HashSet<>();            char[] array = s.word.toCharArray();            for (int i = 0; i < array.length; ++i) {                final char old = array[i];                for (char c = 'a'; c <= 'z'; c++) {                    // 防止同字母替换                    if (c == array[i]) continue;                    array[i] = c;                    State newState = new State(new String(array), s.level+1);                    if (stateIsValid.apply(newState) &&                            !visited.contains(newState)) {                        result.add(newState);                    }                    array[i] = old; // 恢复该单词                }            }            return result;        };        State startState = new State(beginWord, 0);        q.offer(startState);        visited.add(startState);        while (!q.isEmpty()) {            State state = q.poll();            if (stateIsTarget.apply(state)) {                return state.level + 1;            }            HashSet<State> newStates = stateExtend.apply(state);            for (State newState : newStates) {                q.offer(newState);                visited.add(newState);            }        }        return 0;    }    static class State {        String word;        int level;        public State(String word, int level) {            this.word = word;            this.level = level;        }        @Override        public int hashCode() {            return word.hashCode();        }        @Override        public boolean equals(Object other) {            if (this == other) return true;            if (this.hashCode() != other.hashCode()) return false;            if (!(other instanceof State)) return false;            return this.word.equals(((State) other).word);        }    }}

### 双队列​

// Word Ladder// 时间复杂度O(n)，空间复杂度O(n)public class Solution {    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {        Queue<String> current = new LinkedList<>(); // 当前层        Queue<String> next = new LinkedList<>();    // 下一层        HashSet<String> visited = new HashSet<>();  // 判重        int level = -1;  // 层次        final Function<String, Boolean> stateIsValid = (String s) ->                wordList.contains(s) || s.equals(endWord);        final Function<String, Boolean> stateIsTarget = (String s) ->                s.equals(endWord);        final Function<String, HashSet<String> > stateExtend = (String s) -> {            HashSet<String> result = new HashSet<>();            char[] array = s.toCharArray();            for (int i = 0; i < array.length; ++i) {                final char old = array[i];                for (char c = 'a'; c <= 'z'; c++) {                    // 防止同字母替换                    if (c == array[i]) continue;                    array[i] = c;                    String newState = new String(array);                    if (stateIsValid.apply(newState) &&                            !visited.contains(newState)) {                        result.add(newState);                    }                    array[i] = old; // 恢复该单词                }            }            return result;        };        current.offer(beginWord);        visited.add(beginWord);        while (!current.isEmpty()) {            ++level;            while (!current.isEmpty()) {                // 千万不能用 const auto&，pop() 会删除元素，                // 引用就变成了悬空引用                String state = current.poll();                if (stateIsTarget.apply(state)) {                    return level + 1;                }                HashSet<String> newStates = stateExtend.apply(state);                for (String newState : newStates) {                    next.offer(newState);                    visited.add(newState);                }            }            // swap            Queue<String> tmp = current;            current = next;            next = tmp;        }        return 0;    }}