Leetcode - 127. 单词接龙
解题思路参考代码中的注释：
class Solution {
// 为方便后文描述，我们先自定义一个概念：如果两个字符串只有某一位上的字符不同，则称它们为相邻字符串
//
// 我们可以将字符串看作是一个点，如果两个字符串是相邻字符串，则相当于这两个点之间有一条连线
// 那么题目相当于要我们找到从起点到终点的最短路径的长度
//
// 假设起点和终点分别是s和e，且总共有[s-1-2-3-e, s-2-4-e, s-5-6-e]这三条路径，那么可以用广度优先算法：
// 1. 第一层是[e]
// 2. 剩下的点中，与第一层中的点相邻的点就位于第二层，也就是[3, 4, 6]
// 3. 剩下的点中，与第二层中的点相邻的点就位于第三层，也就是[2, 2, 5]
// - 注意，第三层出现了两个2，这是因为从2出发，有两条长度为3的不同的转换路径可以到达终点
// - 在127题中，只需要找到最短路径，此时是可以去重的
// - 但如果要找到所有最短路径（第126题），则不应该去重
// - 这里，我选择不去重，让这部分代码可以同时用于126和127题
// 4. 以此类推，第四层是[1, s]，发现起点在第四层，说明接龙的最短长度就是4
// 注意，一般来说，层数越高，位于该层的点就越多，效率也就降低，因此，为了提高效率，我们使用双向广度优先搜索
// 也就是说分别从起点/终点开始往后/前搜索，哪一层的点的个数少，就用这一层往下搜索
//
// 另一方面，如何找到与某个点相邻的点呢？
// 1. 可以直接遍历wordList，逐个和目标字符串进行比较，看看它们是不是相邻字符串
// 2. 可以枚举出目标字符串的所有相邻字符串，然后看这些相邻字符串是否在wordList中
// 这里我们采用第二种方式，因为第一种方式在wordList长度很大时效率很低
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
return doubleBfs(beginWord, endWord, wordList, new DoubleBfsResultProvider<String, Integer>() {
@Override
public Integer onFail(Layer<String> beginLayer, Layer<String> endLayer) {
return 0;
}
@Override
public Integer onShortestFound(Layer<String> beginLayer, Layer<String> endLayer, Set<String> intersectValues) {
return beginLayer.layerNum() + endLayer.layerNum() - 1;
}
});
}
private static <R> R doubleBfs(String beginWord, String endWord, List<String> wordList, DoubleBfsResultProvider<String, R> provider) {
Set<String> wordSet = new HashSet<>(wordList);
// beginLayer/endLayer代表当前的从起点/终点开始搜索的层
Layer<String> beginLayer = new Layer<>(beginWord);
Layer<String> endLayer = new Layer<>(endWord);
// 如果没有结束单词，则查找失败
if (!wordSet.contains(endWord)) {
return provider.onFail(beginLayer, endLayer);
}
// 题目中说开始单词可能不在wordList中，因此需要手动将开始单词加入wordSet
wordSet.add(beginWord);
// 不断对beginLayer/endLayer进行扩展，直到两者相交或者确定两者无法相交
while (true) {
// 如果beginLayer更小，则对beginLayer进行扩展，而endLayer保持不动；反之同理
boolean beginToEnd = beginLayer.size() <= endLayer.size();
Layer<String> growLayer = beginToEnd ? beginLayer : endLayer;
Layer<String> fixLayer = beginToEnd ? endLayer : beginLayer;
// 记录位于下一层中的单词
Set<String> nextLayerWords = new HashSet<>();
Map<String, List<String>> growMap = new HashMap<>();
for (String word : growLayer.values()) {
List<String> wordNeighbors = new ArrayList<>();
growMap.put(word, wordNeighbors);
// 枚举出该单词的所有相邻字符串
for (int i = 0; i < word.length(); i++) {
char[] arr = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
arr[i] = c;
String neighbor = new String(arr);
// 如果枚举的字符串不在单词字典中，或者当前层已经遍历过该单词，则忽略
if (!wordSet.contains(neighbor) || growLayer.historyContains(neighbor)) {
continue;
}
// 否则枚举的字符串就是当前单词的邻居节点，同时也是位于下一层的单词
wordNeighbors.add(neighbor);
nextLayerWords.add(neighbor);
}
}
}
// 如果下一层没有元素，则一定无法从起点到达终点
if (nextLayerWords.isEmpty()) {
return provider.onFail(beginLayer, endLayer);
}
// 否则，将当前层扩展到下一层
growLayer.grow(growMap);
// 判断两层是否相交，如果是，说明找到了最短路径
Set<String> intersectValues = new HashSet<>(growLayer.values());
intersectValues.retainAll(fixLayer.values());
if (!intersectValues.isEmpty()) {
return provider.onShortestFound(beginLayer, endLayer, intersectValues);
}
}
}
}
/**
* 用于维护位于某一层中的节点，T代表节点的数据类型
* 本类除了记录位于当前层中的节点之外，还会记录这些节点具体是如何演化过来的
* - 比如，假设当前层只有一个节点A，而A有两个相邻节点B和C
* - 那么，经过一次广度优先搜索后，当前层应该存储B和C节点
* - 而在这个过程中，我们会记录下B的前驱结点是A，C的前驱结点是A
*/
class Layer<T> {
/**
* 自定义一个链表节点，用来维护节点存储的数据和节点的演化信息
*/
private static class Node<T> {
T val;
Node<T> pre;
Node(T val, Node<T> pre) { this.val = val; this.pre = pre; }
}
/**
* 本层当前包含的节点及其演化的路径
* 注意，当前层是可能有重复节点的，但这些节点的演化路径一定是不相同的
* 比如，假设节**有"A->B->C"和"A->D->C"两条演化路径，那么本层会存储两个C节点
*/
private LinkedList<Node<T>> paths;
/**
* 当前层包含的节点
*/
private Set<T> currentValues;
/**
* 曾经被本层遍历过的节点
*/
private Set<T> historyValues;
/**
* 本层当前的层数
*/
private int layerNum;
/**
* 初始化，需要调用者提供位于第一层中的节点
*/
public Layer(T... values) {
paths = new LinkedList<>();
currentValues = new HashSet<>();
historyValues = new HashSet<>();
for (T val : values) {
paths.add(new Node<>(val, null));
currentValues.add(val);
historyValues.add(val);
}
layerNum = 1;
}
/**
* 当前层扩展到下一层；growMap中记录了某个节点对应的所有邻居节点
*/
public void grow(Map<T, List<T>> growMap) {
currentValues.clear();
layerNum++;
int size = paths.size();
while (size-- > 0) {
Node<T> node = paths.pollFirst();
for (T neighborVal : growMap.getOrDefault(node.val, Collections.emptyList())) {
paths.add(new Node<>(neighborVal, node));
currentValues.add(neighborVal);
historyValues.add(neighborVal);
}
}
}
/**
* 获取指定节点的演化路径
*/
public List<List<T>> getPathsOf(T val) {
List<List<T>> ret = new ArrayList<>();
for (Node<T> node : this.paths) {
if (node.val.equals(val)) {
List<T> list = new ArrayList<>();
while (node != null) {
list.add(node.val);
node = node.pre;
}
ret.add(list);
}
}
return ret;
}
public Set<T> values() { return Collections.unmodifiableSet(currentValues); }
public int size() { return currentValues.size(); }
public int layerNum() { return layerNum; }
public boolean historyContains(T val) { return historyValues.contains(val); }
}
/**
* 双向广度优先搜索时，使用该类获取计算结果
*/
interface DoubleBfsResultProvider<T, R> {
R onFail(Layer<T> beginLayer, Layer<T> endLayer);
R onShortestFound(Layer<T> beginLayer, Layer<T> endLayer, Set<T> intersectValues);
}