题目
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: 5
解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: 0
解释: endWord “cog” 不在字典中，所以无法进行转换。
我的代码
package LC;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public static int index=0;
public static List<String> templist=new ArrayList<>();
public static int[] Distance(String s1,List<String> wordList) {
//判断各个单词离beginword差几个，用数组接收
int[] arr = new int[wordList.size()];
int index=0;
int ans=0;
for(String s2:wordList) {
for(int i=0;i<s1.length();i++) {
if(s1.charAt(i) != s2.charAt(i)) ans++;
}
arr[index] = ans;
ans=0;
index++;
}
return arr;
}
//递归求步数 至少我感觉应该是递归
public static int Recursion(int i,List<String> wordList) {
//为防出现倒退情况，需要删掉之前走过的路
String str = wordList.get(i);
templist.remove(wordList.get(i));
//arr用来接收这个distance数组
int[] arr =Distance(str,templist);
//如果数组没有1 那index就返回去了
boolean isExist=false;
for(int j:arr) {
if (j==1) isExist=true;
}
if(isExist==false) return 0;
//index此时才能加1
index++;
System.out.println(str);
System.out.println(index);
//现在已知wordlist的第i个离begin只差一个字母，于是对这个单词开始找Distance数组
for(int j=0;j<wordList.size();j++) {
if(arr[j]==1) {
return Recursion(j,templist);
}
}
return 0;
}
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
for(String str:wordList) {
templist.add(str);
}
//arr数组用来接收当前的距离数组，只有数组里包含1时才能行动
int[] arr = Distance(beginWord,wordList);
if(!wordList.contains(endWord)) return 0;
//这个arr1用来保存每一个对应数组下标需要转换的步数,先赋初始值为零
int[] arr1 = new int[wordList.size()];
Arrays.fill(arr1,0);
//假设递归函数已经写好了
for(int i=0;i<arr.length;i++) {
if(arr[i]==1) {
int j=Recursion(i,wordList);
arr1[i]=index;
index=0;
for(String str:wordList) {
templist.add(str);
}
}
}
return 0;
}
public static void main(String[] args) {
String begin = "hit";
String end = "cog";
List<String> list =new ArrayList<String>();
list.add("hot");
list.add("dot");
list.add("dog");
list.add("lot");
list.add("log");
list.add("cog");
ladderLength(begin,end,list);
}
}
代码运行截图
错误分析
- 该代码起的作用只是：查找离beginword相差一个字母的单词并输出，然后接着找离这个单词差一个字母的再次输出，实际上完全没有用到endword。
- 递归也写得很混乱，本意是让递归的return作为最后的步数，但是中途让index+1使递归的return变得比较尴尬，最后成了四不像。
- 该代码无法回头，A->B->C后，无法回头到A->B->D继续求新步数，我也是因此想到深广度优先搜索的，总之开始看答案吧，目前以我的能力写到这里就写不下去了。
思路分析
-
题目让我们求最短路径，看到最短路径，立马想到广度优先算法
-
广度优先算法作为算法的主体，接下来要写出如何判断两个单词只有一个字母不同的算法
-
我去研究广度优先怎么写，自己写试试…
第二次代码
public static boolean DistanceEqual1(String s1,String s2) {
//如果传入String只有一个长度，说明距离必定为1
if(s1.length()==1) return true;
int Distance=0;
for(int i=0;i<s1.length();i++) {
if(s1.charAt(i)==s2.charAt(i)) Distance++;
}
if(Distance==1) return true;
else return false;
}
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
//先判断wordList里面有没有endWord，没有的话直接返回，不可能成功
if(!wordList.contains(endWord)) return 0;
//有的话先将第一个StringNode加入队列
List<String> queue = new ArrayList<String>();
//创建一个保存已经搜索的String的List
List<String> IsSearch = new ArrayList<String>();
//变成node存入队列
queue.add(wordList.get(0));
//存储步数的index
int index=1;
//开始进行遍历
while(!queue.isEmpty()) {
//先取出第一个
String temp = queue.get(0);
//判断这是不是endword
if(temp.equals(endWord)) return index+1;
//首先判断已搜索队列里有没有
if(IsSearch.contains(temp)) {
queue.remove(temp);
continue;
}
else {
//加上已经遍历标识
IsSearch.add(temp);
//步数加一
index++;
//找wordList里离temp距离为1的加入队列，index+1
for(String str:wordList) {
if(DistanceEqual1(str,temp)) {
queue.add(str);
}
}
}
}
return 0;
}
错误分析
-
这次已经写出了一个初步的BFS，但是提交代码运行错误，原因是“a”“b”“c”实现从“a”到“c”的转换时，如果按照队列入队顺序该是a->b->c，可事实只要a->c就行了
-
这次更正的方向暂时定为一次性让队列里所有数据出队并且进行判断，看看能否提交成功。 -
感觉这个错误不常见，于是直接写
else if(wordList.contains(endWord) && beginWord.length()==1) return 2; -
新的错误，在"hot""dog"互转时应该输出0，但实际输出为2。
原因是我的判断距离函数出错了，我统计的是两个string里相同的字符数…我好弱智 -
还是决定放弃index，用Node存parent吧还是，不知道什么错了真是。
-
用Node存是否被搜索过时出错了，因为add时都是new一个并add，所以某些时候会产生死循环，因为是new吧…
-
于是继续采用一个List存储关键字来判断
最终代码
package LC;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
static class Node{
public String str;
public Node parent;
public Node(String str,Node parent) {
this.str=str;
this.parent = parent;
}
}
public static boolean DistanceEqual1(String s1,String s2) {
//如果传入String只有一个长度，说明距离必定为1
if(s1.length()==1) return true;
int Distance=0;
for(int i=0;i<s1.length();i++) {
if(s1.charAt(i)==s2.charAt(i)) Distance++;
}
if(Distance==s1.length()-1) return true;
else return false;
}
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
//先判断wordList里面有没有endWord，没有的话直接返回，不可能成功
if(!wordList.contains(endWord)) return 0;
else if(wordList.contains(endWord) && beginWord.length()==1) return 2;
//有的话先将第一个Node加入队列
List<Node> queue = new ArrayList<Node>();
//用这个存储是否已被搜索
List<String> queue1 = new ArrayList<String>();
//把beginWord存入队列
queue.add(new Node(beginWord,null));
//开始进行遍历
while(!queue.isEmpty()) {
//先取出第一个
Node temp = queue.get(0);
//判断这是不是endword
if(temp.str.equals(endWord)) {
int index=0;
//输出parent的长度
while(temp!=null) {
temp = temp.parent;
index++;
}
return index;
}
//首先判断已搜索队列里有没有
if(queue1.contains(temp.str)) {
queue.remove(temp);
continue;
}else {
//加上已经遍历标识
queue1.add(temp.str);
//找wordList里离temp距离为1的加入队列，index+1
for(String str:wordList) {
if(DistanceEqual1(str,temp.str)) {
queue.add(new Node(str,temp));
}
}
}
//让它出队列
queue.remove(0);
}
return 0;
}
public static void main(String[] args) {
String begin = "hit";
String end = "cog";
List<String> list =new ArrayList<String>();
list.add("hot");
list.add("dot");
list.add("dog");
list.add("lot");
list.add("log");
list.add("cog");
System.out.println(ladderLength(begin,end,list));
}
}
感想
- 由于对算法不熟练，导致过于不敏感，我想了两个小时才隐隐约约想到广度优先遍历，看别人的经验贴直接从最短路径就想到该用广度优先解决了…
- 后面之所以连连报错，是因为并不信任BFS的标准写法，总是觉得自己可以简化一点（比如说不用Node查找parent来计算长度，而是用index，结果连连报错，以及用了Node还不用List存储判断），可能对自己过于自信了。
本文地址：https://blog.csdn.net/z754916067/article/details/109592188
