> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/127.-word-ladder.md).
# 127. Word Ladder - BFS
{% embed url="" %}
####
#### 這題是要找出 start 文字每次換一個字的狀況下, 這字有在 wordlist,
#### 並且能從start string 換字走到 end string, 換最少的數目
## idea:
**無向圖中兩個頂點之間的最短路徑的長度**，可以通過 BFS 遍歷得到
為什麼BFS得到的路徑最短？**可以把起點和終點所在的路徑拉直來看，兩點之間線段最短**；
已知目標頂點的情況下，可以分別從起點和目標頂點（終點）執行 BFS，直到遍歷的部分有交集，這是 BFS 的思想。
#### 有沒有在 wordlist 內, 用 hashset 判斷 contains
此題可以用雙BFS, 目前先用單BFS
main idea:
{% embed url="" %}
time: O(26×wordLen), qsize is too small, ignore?
space: O(26×wordLen)
1. Set put wordList
2. Q.offer(begin)
3. BFS, step = 1
4. replace each char to test set, if set contains endWord, return step+1. else offer Q, remove newword from set
5. step++
6. end return 0
```java
class Solution {
public int ladderLength(String beginWord, String endWord, List wordList) {
Set set = new HashSet<>(wordList);
if (set.size() == 0 || !set.contains(endWord)) {
return 0;
}
set.remove(beginWord);
Queue q = new LinkedList<>();
q.offer(beginWord);
int step = 1;
while (!q.isEmpty()) {
int qSize = q.size();
for (int i = 0; i < qSize; i++) { //BFS固定寫法
String cur = q.poll();
for (int j = 0; j < cur.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) { // 一個一個換字
char[] charArray = cur.toCharArray();
charArray[j] = c;
String newWord = String.valueOf(charArray);
if (set.contains(newWord)) { // 比對是否存在
if (newWord.equals(endWord)) { // 找到 endword 回傳
return step + 1;
}
q.offer(newWord); // 其他狀況 繼續跑
set.remove(newWord); // 移掉找到過的字
}
}
}
}
step++;
}
return 0;
}
}
```
注意這段
```java
char[] charArray = cur.toCharArray(); // 要這時後取出
```
```java
for (char c = 'a'; c <= 'z'; c++) {
char[] charArray = cur.toCharArray();
charArray[j] = c;
String newWord = String.valueOf(charArray);
if (set.contains(newWord)) {
if (newWord.equals(endWord)) {
return step + 1;
}
q.offer(newWord);
set.remove(newWord);
}
}
```
如果charArray在最外面就取出來了, 因為 array不是immutable, 真的會被改掉！
下面這例子,第一個字母跑完後, 直接變最後的 z 了, 不是原本的值了
但如果每次都從頭從cur裡面轉出來, string cur 還是原本的樣子
像這樣的寫法, 最後還要做恢復
所以結論：
要在這裡再取出
## 終止條件移到 poll 之後
this is better, and as the same with leetcode 433
```java
class Solution {
public int ladderLength(String beginWord, String endWord, List wordList) {
if (wordList == null || wordList.size() == 0) return 0;
// use bfs, change word to try to meet wordlist
HashSet set = new HashSet<>(wordList);
set.remove(beginWord);
Queue queue = new LinkedList<>();
queue.offer(beginWord);
int step = 1;
while (!queue.isEmpty()) {
int qSize = queue.size();
for (int q = 0; q < qSize; q++) {
String cur = queue.poll();
if (cur.equals(endWord)) return step; // terminator, if reach endWord
for (int j = 0; j < cur.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) { // 一個一個換字
char[] charArray = cur.toCharArray();
charArray[j] = c;
String newWord = String.valueOf(charArray);
if (set.contains(newWord)) { // 比對是否存在
queue.offer(newWord); // 其他狀況 繼續跑
set.remove(newWord); // 移掉找到過的字
}
}
}
}
step++;
}
return 0;
}
}
```
**為什麼有些題解會需要 visited set? 我這個不需要？**
**因為我的作法在有對應時有對 wordset 做 remove newword, 所以不需要多一個 visited set 來檢查**
## **newest version**
```java
T: O(26*M^2) , M: word_len , N wordList_size, M^2 because new String also needs M
constructing a new string (String.valueOf(cAry)) inside the loop is
O(M) because it involves creating a new character array and copying
M characters into it
S: O(N), set size
```
```java
class Solution {
public int ladderLength(String beginWord, String endWord, List wordList) {
Set set = new HashSet<>(wordList);
if (!set.contains(endWord)) { // there is a edge case
return 0;
}
Queue queue = new LinkedList<>();
queue.offer(beginWord);
int steps = 1; // beginWord is already 1
while (!queue.isEmpty()) {
int size = queue.size();
for (int q = 0; q < size; q++) {
String cur = queue.poll();
if (endWord.equals(cur)) {
return steps;
}
for (int i = 0; i < cur.length(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
char cha[] = cur.toCharArray();
cha[i] = ch;
String newStr = new String(cha);
if (set.contains(newStr)) {
queue.offer(newStr);
set.remove(newStr); //remember to remove
}
}
}
}
steps++;
}
return 0; // cant find endWord from beginWord's transform
}
}
/*
do BFS
hit for each char to replace with 26 chars
if hit wordList put to queue
termial case is equal endWord
*/
```
### key is here
```java
for (int i = 0; i < cur.length(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
char cha[] = cur.toCharArray();
```
and if we don't remove word from set, it will case inf loop,
when doing changes, ok, we geneare dog,
and add to queue, after this it generate hot...
hot generate dog again, and there is still dog in Set -> inf loop!!