# 127. Word Ladder
#### Difficulty: Hard
link: https://leetcode.com/problems/word-ladder/

找shortest path用BFS。

### 1. BFS

這題很多鳥鳥的地方，也是面試的時候需要先與面試官澄清的點。

第一點，beginWord和endWord都可能不在wordList，但題目只提醒beginWord。

第二點，如果建graph的時候，直接檢查wordList裡的每個字是不是鄰居，由於wordList的長度最大是5000，這樣會TLE。

改為用26個英文字母，先生成可能的鄰居word，再檢查是否存在於wordList，Word長度最大是10乘以26字母等於260，就不會TLE。

##### python

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        
        wordList.add(beginWord)
        
        graph = {}
        for word in wordList:
            graph[word] = []
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    if next_word in wordList:
                        graph[word].append(next_word)
        
        length = 1
        visited = {beginWord}
        queue = deque([beginWord])
        while queue:
            length += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                for neigh in graph[node]:
                    if neigh == endWord:
                        return length
                    if neigh not in visited:
                        visited.add(neigh)
                        queue.append(neigh)
        
        return 0

不建graph也行，traverse時再找鄰居有哪些word。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        
        queue = collections.deque([[beginWord, 1]])
        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    if next_word in wordList:
                        wordList.remove(next_word)
                        queue.append([next_word, length + 1])
        return 0

### 2. Bidirectional BFS
進一步優化，不知道從beginWord和endWord哪一邊開始做BFS比較快。

其實，可以兩邊同時做BFS，每一輪都檢查哪一邊的queue長度比較短，就從那邊繼續做BFS，整體來說會比較快。

把wordList當作non visited set，節省空間。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        
        # remove visited word in wordList to prevent BFS from visiting the same word
        wordList.discard(beginWord)
        wordList.discard(endWord)
        
        length = 1
        begin_set, end_set = {beginWord}, {endWord}
        while begin_set and end_set:
            length += 1
            next_set = set()
            for word in begin_set:
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        next_word = word[:i] + c + word[i+1:]
                        if next_word in end_set:
                            return length
                        if next_word in wordList:
                            next_set.add(next_word)
                            wordList.discard(next_word)
            
            begin_set = next_set
            if len(begin_set) > len(end_set):
                begin_set, end_set = end_set, begin_set
        
        return 0

###### tags: `leetcode`