forked from algorithm010/algorithm010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLC127_word_ladder.java
More file actions
132 lines (119 loc) · 4.7 KB
/
LC127_word_ladder.java
File metadata and controls
132 lines (119 loc) · 4.7 KB
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
package Week04;
import java.util.*;
public class LC127_word_ladder {
static class Solution2 {
//建一个canConvert函数，两个单词只有一个字母不同，return true;
public boolean canConvert(String s1, String s2) {
// 因为题目说了单词长度相同，可以不考虑长度问题
// if (s1.length() != s2.length()) return false;
int count = 0;
for (int i = 0; i < s1.length(); ++i) {
if (s1.charAt(i) != s2.charAt(i)) {
++count;
if (count > 1) {
return false;
}
}
}
return count == 1;
}
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) {
return 0;
}
// visited修改为boolean数组
boolean[] visited = new boolean[wordList.size()];
int idx = wordList.indexOf(beginWord);
if (idx != -1) {
visited[idx] = true;
}
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int count = 0;
while (queue.size() > 0) {
int size = queue.size();
++count;
while (size-- > 0) {
String start = queue.poll();
for (int i = 0; i < wordList.size(); ++i) {
// 通过index判断是否已经访问
if (visited[i]) {
continue;
}
String s = wordList.get(i);
if (!canConvert(start, s)) {
continue;
}
if (s.equals(endWord)) {
return count + 1;
}
visited[i] = true;
queue.offer(s);
}
}
}
return 0;
}
}
static class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (wordSet.size() == 0|| !wordSet.contains(endWord)){
return 0;
}
Deque<String> queue = new ArrayDeque<>();
queue.addFirst(beginWord);
Set<String> visited = new HashSet<String>();
visited.add(beginWord);
int step =1;
while (!queue.isEmpty()){
int queSize = queue.size();
for (int i = 0;i<queSize;i++){
String word = queue.pollLast();
char[] wordChar = word.toCharArray();
//build new words
for (int j=0;j<word.length();j++){
//keep original char for backtrack
char originChar = wordChar[j];
for (char k='a'; k<='z';k++){
if (k==originChar){
continue;
}
wordChar[j] = k;
String newWord = String.valueOf(wordChar);
//new word has been visited,continue
if (visited.contains(newWord)){
continue;
}
//new word in the wordList
if (wordSet.contains(newWord)){
//reach to endWord
if (newWord.equals(endWord)){
return step +1;
}
else {
queue.addFirst(newWord);
visited.add(newWord);
}
}
}
//reverse back
wordChar[j] = originChar;
}
}
step++;
}
return 0;
}
}
public static void main(String[] args) {
String beginWord = "hit";
String endWord = "cog";
List<String> wordList = new ArrayList<>();
String[] wordListArray = new String[]{"hot", "dot", "dog", "lot", "log", "cog"};
Collections.addAll(wordList, wordListArray);
Solution solution = new Solution();
int res = solution.ladderLength(beginWord, endWord, wordList);
System.out.println(res);
}
}