LeetCode 面试题 17.22. 单词转换

Categories:

题目描述
思路分析
1. 解法一：BFS 最短路径（推荐）
相似题目

题目描述

✅ 面试题 17.22. 单词转换

思路分析

解法一：BFS 最短路径（推荐）

核心思路：

单词视为图节点，若仅差一个字符则连边。

BFS 从 beginWord 出发，首次到达 endWord 即为最短路径。

记录每个单词的父节点，用于回溯构建答案路径。

复杂度分析：

时间复杂度：O(n · L · 26)，其中 n 为字典单词数，L 为单词长度。

空间复杂度：O(n · L)，用于字典集合、队列与父节点映射。

class Solution {
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) {
            return List.of(beginWord);
        }

        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return new ArrayList<>();
        }

        Queue<String> queue = new ArrayDeque<>();
        Map<String, String> parent = new HashMap<>();
        Set<String> visited = new HashSet<>();

        queue.offer(beginWord);
        visited.add(beginWord);

        boolean found = false;
        while (!queue.isEmpty() && !found) {
            int size = queue.size();
            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) || visited.contains(next)) {
                            continue;
                        }

                        visited.add(next);
                        parent.put(next, cur);
                        queue.offer(next);

                        if (next.equals(endWord)) {
                            found = true;
                            break;
                        }
                    }
                    arr[p] = old;
                    if (found) {
                        break;
                    }
                }
                if (found) {
                    break;
                }
            }
        }

        if (!found) {
            return new ArrayList<>();
        }

        List<String> path = new ArrayList<>();
        String cur = endWord;
        while (cur != null) {
            path.add(cur);
            cur = parent.get(cur);
        }

        Collections.reverse(path);
        return path;
    }
}

func findLadders(beginWord string, endWord string, wordList []string) []string {
	if beginWord == endWord {
		return []string{beginWord}
	}

	dict := map[string]bool{}
	for _, w := range wordList {
		dict[w] = true
	}
	if !dict[endWord] {
		return []string{}
	}

	queue := []string{beginWord}
	visited := map[string]bool{beginWord: true}
	parent := map[string]string{}

	found := false
	for head := 0; head < len(queue) && !found; {
		size := len(queue) - head
		for i := 0; i < size; i++ {
			cur := queue[head]
			head++

			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 !dict[next] || visited[next] {
						continue
					}

					visited[next] = true
					parent[next] = cur
					queue = append(queue, next)

					if next == endWord {
						found = true
						break
					}
				}
				arr[p] = old
				if found {
					break
				}
			}
			if found {
				break
			}
		}
	}

	if !found {
		return []string{}
	}

	path := make([]string, 0)
	cur := endWord
	for cur != "" {
		path = append(path, cur)
		cur = parent[cur]
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	return path
}

相似题目

题目	难度	考察点
127. 单词接龙	困难	BFS
126. 单词接龙 II	困难	BFS + 回溯
433. 最小基因变化	中等	BFS
752. 打开转盘锁	中等	BFS
773. 滑动谜题	困难	BFS

本文作者: HGNULB

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