# **Leetcode筆記(Word Ladder)**

:::info
:information_source: 題目 : Word Ladder, 類型 : graph , 等級 : hard
日期 : 2023/05/18，2023/07/14，2024/04/04
:::

### 嘗試
2023/07/14
關鍵在於剛開始要統計長得很像的字們，把其中的空格加上"*" ，創造一個dict，並且把那些有加星號的組合當作key，那些擁有這種組合的字變成value
pop出一個字的時候，找那個字的各種星星組合，去和dict對應

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        record = defaultdict(list)
        wordList.append(beginWord)
        for w in wordList:
            for i in range(len(beginWord)):
                rest = w[ : i] + "*" + w[i + 1 :]
                record[rest].append(w)
        
        q = deque([beginWord])
        visited = set(beginWord)
        step = 1

        while q:
            length = len(q)
            for _ in range(length):
                w = q.popleft()

                if w == endWord: # 當遇到結尾字
                    return step

                for i in range(len(w)): # 找這個目標字的組成
                    rest = w[ : i] + "*" + w[i + 1 : ]
                    for other in record[rest]:
                        if other not in visited:
                            q.append(other)
                            visited.add(other)
            step += 1

        return 0

2024/04/04
在Python中，deque是一個雙端佇列的資料結構，它接受一個可迭代物件作為參數來初始化佇列。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        record = collections.defaultdict(list)

        for word in wordList:
            for i in range(len(word)):
                w = word[0 : i] + "*" + word[i + 1:]
                record[w].append(word)
        
        step = 1
        q = deque([beginWord])
        visited = set([beginWord]) # 為了避免進入無限迴圈
        while q:
            l = len(q)
            for _ in range(l):
                w = q.popleft()
                if w == endWord:
                    return step
                for i in range(len(w)):
                    new_w = w[0:i] + "*" + w[i + 1:]
                    for next_w in record[new_w]:
                        if next_w not in visited:
                            q.append(next_w)
                            visited.add(next_w)
            step += 1
        
        return 0

---
### **優化**

在給定的程式碼中，`ladderLength` 方法的時間和空間複雜度如下：

1. 建立相似詞字典 (`similar`)：
- 迭代 `wordList` 列表所需時間為 O(|wordList|)，其中 |wordList| 代表單詞列表的長度。
- 對於每個單詞，透過迭代單詞的每個字元來建立模式 (`pattern`)，所需時間為 O(L)，其中 L 代表單詞的平均長度。
- 因此，建立相似詞字典的時間複雜度為 O(|wordList| * L)。

2. BFS 遍歷：
- 在每一層的 BFS 中，需要處理佇列中的每個單詞，所需時間為 O(|q|)，其中 |q| 代表佇列中的單詞數量。
- 對於每個單詞，透過迭代其每個字元來建立模式，所需時間為 O(L)。
- 在相似詞字典中查找相同模式的相似單詞，所需時間為 O(|similar[pattern]|)，其中 |similar[pattern]| 代表具有相同模式的相似單詞的數量。
- 將未訪問過的相似單詞添加到佇列和訪問集合中，所需時間為 O(1)。
- 在最壞的情況下，每個單詞都會被處理一次，因此 BFS 的時間複雜度為 O(|q| * |wordList| * L)。

綜上所述，`ladderLength` 方法的總時間複雜度為 O(|wordList| * L)，其中 |wordList| 代表單詞列表的長度，L 代表單詞的平均長度。

空間複雜度方面：
- 相似詞字典 (`similar`) 的空間複雜度為 O(|wordList| * L)。
- 佇列 (`q`) 和訪問集合 (visited) 的空間複雜度為 O(|wordList|)。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        similar = collections.defaultdict(list)
        wordList.append(beginWord) # beginWord也要在pattern內

        # similar[重複的pattern] = 有哪些word
        for word in wordList:
            for i in range(len(word)):
                # "*ot" / "h*t" / "ho*"
                pattern = word[:i] + "*" + word[i + 1:]
                similar[pattern].append(word)
        
        # 初始化
        q = deque([beginWord])
        visited = set([beginWord])
        res = 1 # 統計bfs次數

        # bfs
        while q:
            for k in range(len(q)): # 這行是為了統計bfs
                word = q.popleft()

                # 符合條件
                if word == endWord:
                    return res

                for i in range(len(word)):
                    pattern = word[:i] + "*" + word[i + 1:]
                    # 去找pattern相同(只差一個字的)
                    for simi_word in similar[pattern]:
                        # 防止重複
                        if simi_word not in visited: 
                            q.append(simi_word)
                            visited.add(simi_word)
            res += 1
        
        return 0

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**


**講解連結**
https://www.youtube.com/watch?v=h9iTnkgv05E&ab_channel=NeetCode
Provided by. NeetCode

###### tags: `graph` `hard` `leetcode`