LeetCode 126. 单词接龙 II

Categories:

题目描述
思路分析
1. 解法一：BFS 分层 + 回溯输出（推荐）
相似题目

题目描述

✅ 126. 单词接龙 II

思路分析

解法一：BFS 分层 + 回溯输出（推荐）

核心思路：

BFS 从 beginWord 出发，按层构建最短路径的父节点关系 parents。

只在同一层内去重，保证记录到的都是最短路径的来源。

找到 endWord 后停止 BFS，再从 endWord 反向 DFS 回溯所有路径。

复杂度分析：

时间复杂度：O(N _ L _ 26)，其中 N 为单词数，L 为单词长度。

空间复杂度：O(N * L)，存储父节点与队列。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Set;

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!dict.contains(endWord)) {
            return res;
        }

        Map<String, List<String>> parents = new HashMap<>();
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(beginWord);

        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        boolean found = false;

        while (!queue.isEmpty() && !found) {
            int size = queue.size();
            Set<String> levelVisited = new HashSet<>();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                char[] arr = cur.toCharArray();
                for (int p = 0; p < arr.length; p++) {
                    char old = arr[p];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == old) {
                            continue;
                        }
                        arr[p] = c;
                        String next = new String(arr);
                        if (!dict.contains(next)) {
                            continue;
                        }
                        if (!visited.contains(next)) {
                            parents.computeIfAbsent(next, k -> new ArrayList<>()).add(cur);
                            if (levelVisited.add(next)) {
                                queue.offer(next);
                            }
                            if (next.equals(endWord)) {
                                found = true;
                            }
                        } else if (levelVisited.contains(next)) {
                            parents.get(next).add(cur);
                        }
                    }
                    arr[p] = old;
                }
            }
            visited.addAll(levelVisited);
        }

        if (!found) {
            return res;
        }

        List<String> path = new ArrayList<>();
        path.add(endWord);
        dfs(endWord, beginWord, parents, path, res);
        return res;
    }

    private void dfs(String word, String begin, Map<String, List<String>> parents,
                     List<String> path, List<List<String>> res) {
        if (word.equals(begin)) {
            List<String> seq = new ArrayList<>(path);
            reverse(seq);
            res.add(seq);
            return;
        }
        List<String> ps = parents.get(word);
        if (ps == null) {
            return;
        }
        for (String p : ps) {
            path.add(p);
            dfs(p, begin, parents, path, res);
            path.remove(path.size() - 1);
        }
    }

    private void reverse(List<String> list) {
        int l = 0;
        int r = list.size() - 1;
        while (l < r) {
            String t = list.get(l);
            list.set(l, list.get(r));
            list.set(r, t);
            l++;
            r--;
        }
    }
}

func findLadders(beginWord string, endWord string, wordList []string) [][]string {
    dict := make(map[string]struct{})
    for _, w := range wordList {
        dict[w] = struct{}{}
    }
    if _, ok := dict[endWord]; !ok {
        return [][]string{}
    }

    parents := make(map[string][]string)
    queue := make([]string, 0)
    queue = append(queue, beginWord)

    visited := make(map[string]struct{})
    visited[beginWord] = struct{}{}

    found := false
    for len(queue) > 0 && !found {
        size := len(queue)
        levelVisited := make(map[string]struct{})
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]

            arr := []byte(cur)
            for p := 0; p < len(arr); p++ {
                old := arr[p]
                for c := byte('a'); c <= byte('z'); c++ {
                    if c == old {
                        continue
                    }
                    arr[p] = c
                    next := string(arr)
                    if _, ok := dict[next]; !ok {
                        continue
                    }
                    if _, ok := visited[next]; !ok {
                        parents[next] = append(parents[next], cur)
                        if _, ok := levelVisited[next]; !ok {
                            levelVisited[next] = struct{}{}
                            queue = append(queue, next)
                        }
                        if next == endWord {
                            found = true
                        }
                    } else {
                        if _, ok := levelVisited[next]; ok {
                            parents[next] = append(parents[next], cur)
                        }
                    }
                }
                arr[p] = old
            }
        }
        for k := range levelVisited {
            visited[k] = struct{}{}
        }
    }

    if !found {
        return [][]string{}
    }

    res := make([][]string, 0)
    path := []string{endWord}
    dfs126(endWord, beginWord, parents, path, &res)
    return res
}

func dfs126(word, begin string, parents map[string][]string, path []string, res *[][]string) {
    if word == begin {
        seq := make([]string, len(path))
        for i := 0; i < len(path); i++ {
            seq[i] = path[len(path)-1-i]
        }
        *res = append(*res, seq)
        return
    }
    ps, ok := parents[word]
    if !ok {
        return
    }
    for _, p := range ps {
        path = append(path, p)
        dfs126(p, begin, parents, path, res)
        path = path[:len(path)-1]
    }
}

相似题目

题目	难度	考察点
127. 单词接龙	困难	BFS
433. 最小基因变化	中等	BFS
752. 打开转盘锁	中等	BFS
934. 最短的桥	中等	BFS
773. 滑动谜题	困难	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/34987661