# 127. Word Ladder - BFS



{% embed url="https://leetcode.com/problems/word-ladder/" %}

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MdqZuDd0MI0EPEaI79X%2F-MdqhdfnmykERqiETkx3%2Fimage.png?alt=media\&token=ea6efa93-4d5b-400e-931c-e428f5ffaed7)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MdqZuDd0MI0EPEaI79X%2F-Mdqhj-AYvWfhi125nwR%2Fimage.png?alt=media\&token=b62542a5-ffa0-41ee-b515-1ad4b84e5f28)



#### &#x20;<a href="#zhe-ti-shi-yao-zhao-chu-start-wen-zi-mei-ci-huan-yi-ge-zi-de-zhuang-kuang-xia-zhe-zi-you-zai-wordlis" id="zhe-ti-shi-yao-zhao-chu-start-wen-zi-mei-ci-huan-yi-ge-zi-de-zhuang-kuang-xia-zhe-zi-you-zai-wordlis"></a>

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MdqZuDd0MI0EPEaI79X%2F-MdqjbNiG1xo7EkEXZzo%2Fimage.png?alt=media\&token=10fb1fe4-2564-4f41-a1be-bc5d2fa9389b)

#### &#x20;這題是要找出 start 文字每次換一個字的狀況下, 這字有在 wordlist, <a href="#zhe-ti-shi-yao-zhao-chu-start-wen-zi-mei-ci-huan-yi-ge-zi-de-zhuang-kuang-xia-zhe-zi-you-zai-wordlis" id="zhe-ti-shi-yao-zhao-chu-start-wen-zi-mei-ci-huan-yi-ge-zi-de-zhuang-kuang-xia-zhe-zi-you-zai-wordlis"></a>



#### 並且能從start string 換字走到 end string, 換最少的數目 <a href="#bing-qie-neng-cong-start-string-huan-zi-zou-dao-end-string-huan-zui-shao-de-shu-mu" id="bing-qie-neng-cong-start-string-huan-zi-zou-dao-end-string-huan-zui-shao-de-shu-mu"></a>

## idea:

**無向圖中兩個頂點之間的最短路徑的長度**，可以通過 BFS 遍歷得到

為什麼BFS得到的路徑最短？**可以把起點和終點所在的路徑拉直來看，兩點之間線段最短**；

&#x20;已知目標頂點的情況下，可以分別從起點和目標頂點（終點）執行 BFS，直到遍歷的部分有交集，這是 BFS 的思想。

#### 有沒有在 wordlist 內, 用 hashset 判斷 contains



此題可以用雙BFS, 目前先用單BFS

[https://leetcode.com/problems/word-ladder/discuss/40704/Java-Solution-using-BFS-with-explanation](https://leetcode.com/problems/word-ladder/discuss/40704/Java-Solution-using-BFS-with-explanation)



main idea:

{% embed url="https://leetcode-cn.com/problems/word-ladder/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you-2/" %}



time: O(26×wordLen), qsize is too small, ignore?

space: O(26×wordLen)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCkxdJYDcgItwkLAWoQ%2F-MCl-MCeYn-kaYA0V_Zm%2Fimage.png?alt=media\&token=839b6e91-cd03-40a4-a4be-edd1571d9a54)

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<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (set.size() == 0 || !set.contains(endWord)) {
            return 0;
        }
        set.remove(beginWord);
        
        Queue<String> 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);
    }

}
```



&#x20;如果charArray在最外面就取出來了, 因為 array不是immutable, 真的會被改掉！

下面這例子,第一個字母跑完後, 直接變最後的 z 了, 不是原本的值了

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCl1H9TJ1uFsSCQ8vqz%2F-MClD9PYnV2ojRYbonXJ%2Fimage.png?alt=media\&token=6f2b415c-6d71-4e62-acfd-084b6efe22fc)



但如果每次都從頭從cur裡面轉出來, string cur 還是原本的樣子

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCl1H9TJ1uFsSCQ8vqz%2F-MClDw5DvzWCs4E9mlj4%2Fimage.png?alt=media\&token=ee547712-0c3b-403a-ba54-af5a52f04e80)

像這樣的寫法, 最後還要做恢復

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCl1H9TJ1uFsSCQ8vqz%2F-MClDiRRsGqmJ8c2WOCA%2Fimage.png?alt=media\&token=1fc36524-ea70-46c7-a40c-fd9a95fa95c1)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCl1H9TJ1uFsSCQ8vqz%2F-MClDr3gNejpDc_Y9buy%2Fimage.png?alt=media\&token=127ee097-2cb0-4ca0-b113-ae1ea9d5ca5e)



所以結論：

要在這裡再取出

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MCl1H9TJ1uFsSCQ8vqz%2F-MClE3bPrQJq6AfODzDH%2Fimage.png?alt=media\&token=71092156-b730-465c-816f-68ab75718579)



## 終止條件移到 poll 之後

this is better, and as the same with leetcode 433

```java
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0) return 0;
        // use bfs, change word to try to meet wordlist
        HashSet<String> set = new HashSet<>(wordList);
        set.remove(beginWord);
        
        Queue<String> 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<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) { // there is a edge case
            return 0;
        }
        Queue<String> 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,&#x20;



<figure><img src="https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FXHbJNL4AQ3Rvx7MXWzpv%2Fimage.png?alt=media&#x26;token=21895d61-1591-4460-aae3-aa0bb44e75ac" alt=""><figcaption></figcaption></figure>

when doing changes, ok, we geneare dog,&#x20;

and add to queue, after this it generate hot...

hot generate dog again, and there is still dog in Set -> inf loop!!
