127-word-ladder.md Added Python solution.

gazeldx · gazeldx · commit 1071c14c5b97 · 2024-12-18T12:57:59.000+08:00
diff --git a/.gitignore b/.gitignore
@@ -2,3 +2,4 @@
 temp/
 solutions/empty-template.md
 solutions/empty-template-with-images.md
+/solutions/leetcode-solution-common.md
diff --git a/README.md b/README.md
@@ -68,5 +68,6 @@ You can skip the more difficult problems and do them later.
 - [200. Number of Islands](solutions/1-1000/200-number-of-islands.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_ and **3** solutions.
 - [695. Max Area of Island](solutions/1-1000/695-max-area-of-island.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_.
 - [827. Making A Large Island](solutions/1-1000/827-making-a-large-island.md) was solved in _Python_.
+- [127. Word Ladder](solutions/1-1000/127-word-ladder.md) was solved in _Python_.
 
 More LeetCode problems will be added soon...
diff --git a/images/127.png b/images/127.png
diff --git a/images/42.png b/images/42.png
diff --git a/solutions/1-1000/127-word-ladder.md b/solutions/1-1000/127-word-ladder.md
@@ -0,0 +1,164 @@
+# LeetCode 127. Word Ladder's Solution
+LeetCode problem link: [127. Word Ladder](https://leetcode.com/problems/word-ladder/)
+
+## LeetCode problem description
+A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:
+
+* Every adjacent pair of words differs by a single letter.
+* Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
+* `sk == endWord`
+
+Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return **the number of words** in the **shortest transformation sequence** from `beginWord` to `endWord`, or `0` if no such sequence exists.
+
+### Example 1
+```
+Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
+Output: 5
+Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
+```
+
+### Example 2
+```
+Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
+Output: 0
+Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
+```
+
+### Constraints
+- `1 <= beginWord.length <= 10`
+- `endWord.length == beginWord.length`
+- `1 <= wordList.length <= 5000`
+- `wordList[i].length == beginWord.length`
+- `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
+- `beginWord != endWord`
+- All the words in `wordList` are **unique**.
+
+## Intuition
+This problem is hard. Before solving this problem, you can do the following problem first:
+
+- [200. Number of Islands (Solution 3: Breadth-First Search)](200-number-of-islands-3.md)
+
+The **word transformation sequence** problem can be abstracted into a **graph theory** problem. And it is an **undirected graph**:
+
+![](../../images/127.png)
+
+### Breadth-First Search
+![](../../images/binary_tree_BFS_1.gif)
+
+* As shown in the figure above, **breadth-first search** can be thought of as visiting nodes in rounds and rounds. Actually, whenever you see a question is about
+getting `shortest` or `least` of something of a graph, `breadth-first search` would probably help.
+
+* `breadth-first search` emphasizes first-in-first-out, so a **queue** is needed.
+
+## Approach
+1. `Breadth-First Search` a graph means traversing **from near to far**, from `circle 1` to `circle N`. Each `circle` is a round of iteration, but we can simplify it by using just 1 round.
+1. So through `Breadth-First Search`, when a word matches `endWord`, the game is over, and we can return the number of **circle** as a result.
+
+## Complexity
+* Time: `O(n * n)`.
+* Space: `O(n * n)`.
+
+## Python
+```python
+class Solution:
+    def __init__(self):
+        self.word_set = None
+        self.endWord = None
+        self.queue = deque()
+
+    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
+        self.endWord = endWord
+        self.word_set = set(wordList)
+
+        if endWord not in self.word_set:
+            return 0
+        
+        self.queue.append((beginWord, 1))
+
+        return self.breadth_first_search()
+
+    def breadth_first_search(self):
+        while self.queue:
+            word0, circle = self.queue.popleft()
+            removed_words = set()
+
+            for word in self.word_set:
+                if one_char_different(word, word0):
+                    if word == self.endWord:
+                        return circle + 1
+
+                    self.queue.append((word, circle + 1))
+
+                    removed_words.add(word)
+            
+            self.word_set -= removed_words
+        
+        return 0
+
+
+def one_char_different(word1, word2):
+    different_char_count = 0
+
+    for i in range(len(word1)):
+        if word1[i] != word2[i]:
+            different_char_count += 1
+            if different_char_count > 1:
+                return False
+    
+    return True
+```
+
+## Java
+```java
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## C++
+```cpp
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## JavaScript
+```javascript
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## C#
+```c#
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## Go
+```go
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## Ruby
+```ruby
+# Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## C
+```c
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## Kotlin
+```kotlin
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## Swift
+```swift
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## Rust
+```rust
+// Welcome to create a PR to complete the code of this language, thanks!
+```
+
+## Other languages
+```
+// Welcome to create a PR to complete the code of this language, thanks!
+```
diff --git a/solutions/1-1000/200-number-of-islands-3.md b/solutions/1-1000/200-number-of-islands-3.md
@@ -66,6 +66,7 @@ Please click [Depth-First Search by Iteration Solution](200-number-of-islands-2.
 ![](../../images/binary_tree_BFS_1.gif)
 
 As shown in the figure above, **breadth-first search** can be thought of as visiting nodes in rounds and rounds.
+
 It emphasizes first-in-first-out, so a **queue** is needed.
 
 ## Complexity
diff --git a/solutions/1-1000/42-trapping-rain-water-2.md b/solutions/1-1000/42-trapping-rain-water-2.md
@@ -33,7 +33,7 @@ This solution will follow **Monotonic Stack**'s common rule: **only calculating
 
 This common rule can be applied to calculating result for **most** of the **Monotonic Stack** problems.
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 ### Solution 1
 Please click [42. Trapping Rain Water (solution 1)](42-trapping-rain-water.md) to see it.
@@ -97,7 +97,7 @@ class Solution:
         return result
 ```
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 ## C++
 ```cpp
@@ -161,7 +161,7 @@ var trap = function (heights) {
 };
 ```
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 ## C#
 ```c#
@@ -228,7 +228,7 @@ func trap(heights []int) int {
 }
 ```
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 ## Ruby
 ```ruby
diff --git a/solutions/1-1000/42-trapping-rain-water.md b/solutions/1-1000/42-trapping-rain-water.md
@@ -36,7 +36,7 @@ This problem can be solved using **Monotonic Stack**.
     1) The right side (current item) is **no shorter** than the left side (the top of stack).
     2) The right side (current item) is **shorter** than the left side (the top of stack).
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 Detailed solutions will be given later, and now only the best practices in 7 languages are given.
 
@@ -108,7 +108,7 @@ class Solution:
         return result
 ```
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 ## C++
 ```cpp
@@ -174,7 +174,7 @@ var trap = function (heights) {
 };
 ```
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 ## C#
 ```c#
@@ -246,7 +246,7 @@ func trap(heights []int) int {
 }
 ```
 
-![](../../images/0042.png)
+![](../../images/42.png)
 
 ## Ruby
 ```ruby
diff --git a/solutions/1-1000/827-making-a-large-island.md b/solutions/1-1000/827-making-a-large-island.md
@@ -35,7 +35,7 @@ Explanation: Can't change any 0 to 1, only one island with area = 4.
 - `grid[i][j]` is either `0` or `1`.
 
 ## Intuition
-This problem is hard. Before solving this problem, you can do the following two problems first.
+This problem is hard. Before solving this problem, you can do the following two problems first:
 
 - [200. Number of Islands](200-number-of-islands.md)
 - [695. Max Area of Island](695-max-area-of-island.md)
