127. Word Ladder - BFS

Loading...LeetCode

這題是要找出 start 文字每次換一個字的狀況下, 這字有在 wordlist,

並且能從start string 換字走到 end string, 換最少的數目

idea:

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

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

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

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

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

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

main idea:

力扣

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

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;
    }
}

注意這段

char[] charArray = cur.toCharArray(); // 要這時後取出

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

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

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

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

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!!