🌕 🌕 🌗 127. 单词接龙

难度: 🌕 🌕 🌗

问题描述

---

解法

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 思路：
        // 求最短路径 - 广度优先 - 搜到即可返回
        int amount = wordList.size();
        HashSet<String> set  = new HashSet<>();
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int res = 0;
        while(!queue.isEmpty()) {
            res ++;
            int len = queue.size();
            for(int i = 0; i < len; i ++) {
                String cur = queue.poll();
                // 找 cur 可以到达的 next
                List<String> list = getList(wordList, amount, set, cur);
                for(int j = 0; j < list.size(); j ++) {
                    String next = list.get(j);
                    // System.out.println(cur + "   " + next  + "   " + res);
                    if(next.equals(endWord)) {
                        return res + 1;
                    }
                    set.add(next);
                    queue.offer(next);
                }
            }
        }
        return 0;
    }

    private List<String> getList(List<String> wordList, int len, HashSet<String> set, String cur) {
        List<String> res = new ArrayList<>();
        for(int i = 0; i < len; i ++) {
            String next = wordList.get(i);
            if(!set.contains(next)) {
                if(isValid(cur, next)) {
                    res.add(next); // 不再该方法内部修改 set
                }
            }
        }
        return res;
    }

    private boolean isValid(String a, String b) {
        int len = a.length();
        int diff = 0;
        for(int i = 0; i < len; i ++) {
            if(a.charAt(i) != b.charAt(i)) {
                if(diff == 0) {
                    diff ++;
                } else {
                    return false;
                }
            }
        }
        return diff == 1;
    }
}

---

输出

---

解法 2 - 双向广度遍历

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 思路：
        // 双向广度遍历，每次遍历选择节点数少的一侧进行遍历
        int len = wordList.size();
        wordList.add(beginWord); // 将 beginWord 添加进字典范围
        if(wordList.indexOf(endWord) < 0) {
            return 0; // 字典中不存在 endWord，不可能到达
        }
        LinkedList<String> queue1 = new LinkedList<>();
        HashSet<String> set1 = new HashSet<>();
        queue1.offer(beginWord);
        set1.add(beginWord);
        LinkedList<String> queue2 = new LinkedList<>();
        HashSet<String> set2 = new HashSet<>();
        queue2.offer(endWord);
        set2.add(endWord);
        int res = 2;
        while(!queue1.isEmpty() && !queue2.isEmpty()) {
            // 选择节点个数少的一侧
            int len1 = queue1.size();
            int len2 = queue2.size();
            if(len2 < len1) {
                // 交换
                LinkedList<String> tmpQ = queue1;
                queue1 = queue2;
                queue2 = tmpQ;
                HashSet<String> tmpS = set1;
                set1 = set2;
                set2 = tmpS;
                len1 = len2;
            }
            // 每次都从 queue1 中取出节点
            res ++;
            for(int i = 0; i < len1; i ++) {
                // System.out.println(len1);
                String cur = queue1.poll(); // 当前层某个节点
                // 遍历 wordList 查找 next
                for(int j = 0; j < len; j ++) {
                    String next = wordList.get(j);
                    if(set1.contains(next)) {
                        continue; // 这个方向已经遍历过该节点
                    }
                    if(!isValid(cur, next)) {
                        continue;
                    }
                    // System.out.println(cur + "  " + next + "   " + res);
                    // 符合要求的 next 节点，判断另一侧是否已经有了该节点
                    if(set2.contains(next)) {
                        return res - 1;
                    } else {
                        set1.add(next);
                        queue1.offer(next);
                    }
                }
            }
        }
        return 0;
    }

    private boolean isValid(String a, String b) {
        int len = a.length();
        int diff = 0;
        for(int i = 0; i < len; i ++) {
            if(a.charAt(i) != b.charAt(i)) {
                if(diff == 0) {
                    diff ++;
                } else {
                    return false;
                }
            }
        }
        return diff == 1;
    }
}

---

输出 2