题目描述
有一个单词列表，一个初始单词和一个最终单词，初始单词需要通过单词列表逐步变换到最终单词，求变换所需的最短变换路径长度。
变换规则：每次只能变动1个字母（不可交换位置，如：从abc变成cba属于变动了2个字母），每次变换只能从单词列表中选取。
例如：初始单词hot，最终单词dog，单词列表[got, dot, god, dog, lot, log]，最短变换路径为[hot,dot,dog]，最短变换路径长度为3。
注：单词列表中包含最终单词，不包含初始单词；列表中每一项单词长度与初始单词、最终单词相同；列表中单词不重复；所有字母均为小写。
思路
BFS。
每次将差一个字符且之前未添加的单词加入list，遍历list是一个一个遍历，即广度优先，直到找到到目标单词的最短路径
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| import java.util.ArrayList;
import java.util.Scanner;
public class Main {
class Node{
String string;
int count;
public Node(String string, int count) {
this.string = string;
this.count = count;
}
}
public ArrayList<String> list;
public String head;
public String tail;
public ArrayList<Node> res;
public static void main(String[] args) {
Main main = new Main();
main.init();
System.out.println(main.calculating());
}
public int calculating() {
res = new ArrayList<>();
res.add(new Node(head, 1));
int index = 0; // 当前访问的hashMap下标
while(index < res.size()) {
Node node = res.get(index++);
String tar = node.string;
for(String string : list) {
if(isOneDiff(tar, string)) { // 如果只比tar差一个字符
if(!containString(string)) { // 如果没访问过string
if(isOneDiff(tail, string)) { // 满足条件，输出结果
return node.count+2;
}else {
res.add(new Node(string, node.count+1));
}
}
}
}
}
return 0;
}
public boolean containString(String string) {
for(Node node : res) {
if(node.string.equals(string)) {
return true;
}
}
return false;
}
public boolean isOneDiff(String tar, String tmp) {
int count = 0;
for(int i = 0; i < tar.length(); i++) {
if(tar.charAt(i) != tmp.charAt(i)) {
count++;
}
}
return count == 1;
}
public void init() {
Scanner scanner = new Scanner(System.in);
head = scanner.nextLine();
tail = scanner.nextLine();
list = new ArrayList<>();
while(scanner.hasNext()) {
String string = scanner.next();
if(!string.equals(tail)) { // 不加入tail
list.add(string);
}
}
}
}
|
考察点