Merge branch 'master' of github.com:soapyigu/LeetCode_Swift

soapyigu · soapyigu · commit 45126d346e9d · 2020-01-04T11:23:57.000-08:00
diff --git a/BFS/WordLadder.swift b/BFS/WordLadder.swift
@@ -10,41 +10,41 @@
 
 class WordLadder {
     func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
-        var words = Set(wordList)
-        var qWordStep = [(beginWord, 1)]
+        guard beginWord.count == endWord.count else {
+            return 0
+        }
+        
+        var queue = [(beginWord, 1)], wordSet = Set<String>(wordList)
         
-        while !qWordStep.isEmpty {
-            let (currentWord, currentStep) = qWordStep.removeFirst()
+        while !queue.isEmpty {
+            let (word, step) = queue.removeFirst()
             
-            if currentWord == endWord {
-                return currentStep
+            if word == endWord {
+                return step
             }
             
-            for (i, currentWordChar) in currentWord.enumerated() {
+            // transform word
+            for i in 0..<word.count {
+                var wordArray = Array(word)
+                
                 for char in "abcdefghijklmnopqrstuvwxyz" {
-                    if char != currentWordChar {
-                        let newWord = currentWord.replace(at: i, to: char)
-                        
-                        if words.contains(newWord) {
-                            qWordStep.append((newWord, currentStep + 1))
-                            
-                            words.remove(newWord)
-                        }
+                    guard char != wordArray[i] else {
+                        continue
                     }
+                    
+                    wordArray[i] = char
+                    let transformedWord = String(wordArray)
+                    
+                    guard wordSet.contains(transformedWord) else {
+                        continue
+                    }
+                    
+                    wordSet.remove(transformedWord)
+                    queue.append((transformedWord, step + 1))
                 }
             }
         }
         
         return 0
     }
 }
-
-extension String {
-    func replace(at index: Int, to char: Character) -> String {
-        var chars = Array(self)
-        
-        chars[index] = char
-        
-        return String(chars)
-    }
-}
diff --git a/README.md b/README.md
@@ -184,8 +184,8 @@
 | ----- | -------- | ---------- | ---- | ----- |
 [Same Tree](https://oj.leetcode.com/problems/same-tree/)| [Swift](./Tree/SameTree.swift)| Easy| O(n)| O(n)|
 [Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)| [Swift](./Tree/SymmetricTree.swift)| Easy| O(n)| O(n)|
-[Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)| [Swift](./Tree/InvertBinaryTree)| Easy| O(n)| O(n)|
-[Binary Tree Upside Down](https://leetcode.com/problems/binary-tree-upside-down/)| [Swift](./Tree/BinaryTreeUpsideDown)| Medium| O(n)| O(1)|
+[Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)| [Swift](./Tree/InvertBinaryTree.swift)| Easy| O(n)| O(n)|
+[Binary Tree Upside Down](https://leetcode.com/problems/binary-tree-upside-down/)| [Swift](./Tree/BinaryTreeUpsideDown.swift)| Medium| O(n)| O(1)|
 [Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/)| [Swift](./Tree/MinimumDepthOfBinaryTree.swift)| Easy| O(n)| O(1)|
 [Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)| [Swift](./Tree/MaximumDepthOfBinaryTree.swift)| Easy| O(n)| O(1)|
 [Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/)| [Swift](./Tree/DiameterBinaryTree.swift)| Easy| O(n)| O(1)|
