力扣面试150题--单词接龙
Day 66
题目描述
思路
初次做法：
直接把上一题最小基于变化的代码拿来修改后使用
class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Map<String,Integer> tes=new HashMap<String,Integer>();if(wordList.size()==0){if(beginWord.equals(endWord)){return 1;}return -1;}int min=10000;ArrayList<String> list = new ArrayList<>();for (int i = 0; i < wordList.size(); i++) {tes.put(wordList.get(i),i);//添加bank和i的映射list.add(wordList.get(i));}//单独处理startgeneint start=0;int end=0;if(tes.containsKey(endWord)){end=tes.get(endWord);}else{return 0;}if(tes.containsKey(beginWord)){start=tes.get(beginWord);}else{tes.put(beginWord,list.size());start=list.size();list.add(beginWord);}boolean[]visited=new boolean[list.size()];//访问数组if(start==end){return 0;//说明就一个基因}else{//构建graphint[][] graph=new int[list.size()][list.size()];for (int i=0;i<list.size();i++){for(int j=i;j<list.size();j++){String a=list.get(i);String b=list.get(j);int x=tes.get(a);int y=tes.get(b);int change=0;for (int k=0;k<a.length();k++){if(a.charAt(k)!=b.charAt(k)){change++;}if(change>1){//说明一步到不了break;}}if(change==1){graph[x][y]=1;graph[y][x]=1;}else{graph[x][y]=10;graph[y][x]=10;}}}for (int j = 0; j < graph.length; j++) {graph[j][j]=0;}//构造完成Queue<int[]>res=new LinkedList<int[]>();res.add(new int[]{start,0});while(!res.isEmpty()){int[] temp=res.poll();int x=temp[0];int y=temp[1];visited[x]=true;//访问过了for(int k=0;k<graph.length;k++){if(graph[x][k]==1&&!visited[k]){//说明一步能达到if(k!=end){res.offer(new int[]{k,y+1});}else{if(y+1<min){min=y+1;}}}}}}if(min!=10000){return min+1;}return 0;//变化不了}}
结果出现问题了，发现超时了，经过分析后，发现在于构造graph时，每个单词进行两两比较，花费时间过多，因此针对这个点进行优化。
优化后思路：
分析一下，我们进行两两比较字符串的目的是为了找到能一步到达的字符串，那么换种思路，对于一个单词而言，从头到尾修改任意一个字母，都算一步能到达的字符串，于是想到了通配符。
优化 ：传统方法需要比较 任意两个单词，时间复杂度为 O (n²L)。而通配符预处理通过哈希表快速匹配相邻单词，将时间复杂度降低到 O (nL²)。
举个例子单词 “hit”，可以生成 3 种通配符模式：
!it（替换第 1 个字符为 ! ）
h!t（替换第 2 个字符为 !）
hi!（替换第 3 个字符为 !）
于是产生以下做法：
- 对于每个单词，生成所有可能的通配符模式（每个位置替换为 *）。
- 使用哈希表 wildcardMap 记录每个模式对应的单词列表。
- 遍历 wildcardMap 中的每个模式，将共享同一模式的单词两两连接。
class Solution {public List<String> generateWildcardPatterns(String word) {//生成通配符List<String> patterns = new ArrayList<>();char[] chars = word.toCharArray();for (int i = 0; i < chars.length; i++) {char original = chars[i];chars[i] = '*';patterns.add(new String(chars));chars[i] = original; // 恢复原字符}return patterns;}public int ladderLength(String beginWord, String endWord, List<String> wordList) {Map<String,Integer> tes=new HashMap<String,Integer>();if(wordList.size()==0){if(beginWord.equals(endWord)){return 1;}return -1;}int min=10000;ArrayList<String> list = new ArrayList<>();for (int i = 0; i < wordList.size(); i++) {tes.put(wordList.get(i),i);//添加bank和i的映射list.add(wordList.get(i));}//单独处理startgeneint start=0;int end=0;if(tes.containsKey(endWord)){end=tes.get(endWord);}else{return 0;}if(tes.containsKey(beginWord)){start=tes.get(beginWord);}else{tes.put(beginWord,list.size());start=list.size();list.add(beginWord);}boolean[]visited=new boolean[list.size()];//访问数组if(start==end){return 0;//说明就一个基因}else{//构建graphint[][] graph=new int[list.size()][list.size()];// 2. 预处理通配符模式Map<String, List<Integer>> wildcardMap = new HashMap<>();for (int i = 0; i < list.size(); i++) {String word = list.get(i);for (String pattern : generateWildcardPatterns(word)) {wildcardMap.computeIfAbsent(pattern, k -> new ArrayList<>()).add(i);//在 Map 中查找或创建一个列表，并向列表添加元素}}// 3. 构建邻接矩阵（基于通配符模式）for (List<Integer> group : wildcardMap.values()) {for (int i = 0; i < group.size(); i++) {int u = group.get(i);for (int j = i + 1; j < group.size(); j++) {int v = group.get(j);graph[u][v] = 1; // 无向图，双向标记graph[v][u] = 1;}}}//构造完成Queue<int[]>res=new LinkedList<int[]>();res.add(new int[]{start,0});while(!res.isEmpty()){int[] temp=res.poll();int x=temp[0];int y=temp[1];visited[x]=true;//访问过了for(int k=0;k<graph.length;k++){if(graph[x][k]==1&&!visited[k]){//说明一步能达到if(k!=end){res.offer(new int[]{k,y+1});}else{return y+2;}}}}}if(min!=10000){return min+1;}return 0;//变化不了}}
虽然通过了但是时间复杂度还是很高
题解思路：
双向bfs算法，在之前代码的基础上，不仅从起点往终点搜索，同时从终点向起始搜索，记录变化的距离，直到两者变化到同一种情况，将距离相加即可，
class Solution {// 生成单词的所有通配符模式（例如："hit" -> ["*it", "h*t", "hi*"]）public List<String> generateWildcardPatterns(String word) {List<String> patterns = new ArrayList<>();char[] chars = word.toCharArray();for (int i = 0; i < chars.length; i++) {char original = chars[i];chars[i] = '*';patterns.add(new String(chars));chars[i] = original; // 恢复原字符}return patterns;}public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 检查终点是否存在于字典中，不存在则无法转换if (!wordList.contains(endWord)) {return 0;}// 预处理通配符模式Map<String, List<Integer>> wildcardMap = new HashMap<>();List<String> allWords = new ArrayList<>(wordList);// 确保起点在单词列表中if (!allWords.contains(beginWord)) {allWords.add(beginWord);}// 为每个单词生成通配符模式并记录映射关系for (int i = 0; i < allWords.size(); i++) {String word = allWords.get(i);for (String pattern : generateWildcardPatterns(word)) {// 将单词索引添加到对应通配符模式的列表中wildcardMap.computeIfAbsent(pattern, k -> new ArrayList<>()).add(i);}}// 构建邻接矩阵（表示单词间的连接关系）int n = allWords.size();int[][] graph = new int[n][n];// 遍历每个通配符模式，将共享同一模式的单词两两连接for (List<Integer> group : wildcardMap.values()) {for (int i = 0; i < group.size(); i++) {int u = group.get(i);for (int j = i + 1; j < group.size(); j++) {int v = group.get(j);graph[u][v] = 1; // 无向图，双向标记graph[v][u] = 1;}}}// 获取起点和终点在单词列表中的索引int start = allWords.indexOf(beginWord);int end = allWords.indexOf(endWord);// 双向BFS初始化// 正向搜索相关数据结构boolean[] visitedBegin = new boolean[n]; // 记录正向已访问节点int[] distanceBegin = new int[n]; // 记录从起点到各节点的距离Arrays.fill(distanceBegin, Integer.MAX_VALUE); // 初始化为无穷大distanceBegin[start] = 0; // 起点距离为0visitedBegin[start] = true; // 标记起点已访问Queue<Integer> queueBegin = new LinkedList<>(); // 正向BFS队列queueBegin.offer(start); // 起点入队// 反向搜索相关数据结构boolean[] visitedEnd = new boolean[n]; // 记录反向已访问节点int[] distanceEnd = new int[n]; // 记录从终点到各节点的距离Arrays.fill(distanceEnd, Integer.MAX_VALUE); // 初始化为无穷大distanceEnd[end] = 0; // 终点距离为0visitedEnd[end] = true; // 标记终点已访问Queue<Integer> queueEnd = new LinkedList<>(); // 反向BFS队列queueEnd.offer(end); // 终点入队// 双向BFS搜索while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {// 从起点扩展一层// 保存当前层的节点数量int sizeBegin = queueBegin.size();for (int i = 0; i < sizeBegin; i++) {int curr = queueBegin.poll();// 检查是否与反向搜索相遇if (visitedEnd[curr]) {// 返回总距离（正向距离 + 反向距离 + 1）// +1是因为两个方向都计算了自己的步数return distanceBegin[curr] + distanceEnd[curr] + 1;}// 扩展当前节点的所有邻居for (int neighbor = 0; neighbor < n; neighbor++) {if (graph[curr][neighbor] == 1 && !visitedBegin[neighbor]) {distanceBegin[neighbor] = distanceBegin[curr] + 1; // 更新距离visitedBegin[neighbor] = true; // 标记已访问queueBegin.offer(neighbor); // 邻居入队}}}// 从终点扩展一层// 保存当前层的节点数量int sizeEnd = queueEnd.size();for (int i = 0; i < sizeEnd; i++) {int curr = queueEnd.poll();// 检查是否与正向搜索相遇if (visitedBegin[curr]) {// 返回总距离return distanceBegin[curr] + distanceEnd[curr] + 1;}// 扩展当前节点的所有邻居for (int neighbor = 0; neighbor < n; neighbor++) {if (graph[curr][neighbor] == 1 && !visitedEnd[neighbor]) {distanceEnd[neighbor] = distanceEnd[curr] + 1; // 更新距离visitedEnd[neighbor] = true; // 标记已访问queueEnd.offer(neighbor); // 邻居入队}}}}return 0; // 无法从起点转换到终点}
}