[Array] Add a solution to Verifying an Alien Dictionary

soapyigu · soapyigu · commit fa1c4a907ec2 · 2020-01-12T14:36:09.000-08:00
diff --git a/Array/VerifyingAlienDictionary.swift b/Array/VerifyingAlienDictionary.swift
@@ -0,0 +1,40 @@
+/**
+ * Question Link: https://leetcode.com/problems/verifying-an-alien-dictionary/
+ * Primary idea: Compare words one by one and make sure they are following the order
+ *
+ * Time Complexity: O(n), Space Complexity: O(n)
+ *
+ */
+
+ class VerifyingAlienDictionary {
+    func isAlienSorted(_ words: [String], _ order: String) -> Bool {
+        let charToOrder = Dictionary(uniqueKeysWithValues: order.enumerated().map { ($0.1, $0.0) })
+        
+        for i in 0..<words.count - 1 {
+            let currentWord = Array(words[i]), nextWord = Array(words[i + 1])
+            var j = 0
+            
+            while j < min(currentWord.count, nextWord.count) {
+                let currentChar = currentWord[j], nextChar = nextWord[j]
+                
+                guard currentChar != nextChar else {
+                    j += 1
+                    continue
+                }
+                
+                if charToOrder[currentChar]! > charToOrder[nextChar]! {
+                    return false
+                } else {
+                    break
+                }
+            }
+            
+            // edge case: "apple" vs. "app"; "kuvp" vs. "q"
+            if j == nextWord.count && currentWord.count > nextWord.count {
+                return false
+            }
+        }
+        
+        return true
+    }
+}
diff --git a/README.md b/README.md
@@ -42,6 +42,7 @@
 ## Array
 | Title | Solution | Difficulty | Time | Space |
 | ----- | -------- | ---------- | ---- | ----- |
+[Verify an Alien Dictionary](https://leetcode.com/problems/verifying-an-alien-dictionary/)|[Swift](Array/VerifyingAlienDictionary.swift)| Easy| O(n)| O(n)|
 [Sort Array By Parity](https://leetcode.com/problems/sort-array-by-parity/)|[Swift](Array/SortArrayByParity.swift)| Easy| O(n)| O(n)|
 [Max Consecutive Ones](https://leetcode.com/problems/max-consecutive-ones/)| [Swift](./Array/MaxConsecutiveOnes.swift)| Easy| O(n)| O(1)|
 [Heaters](https://leetcode.com/problems/heaters/)| [Swift](./Array/Heaters.swift)| Easy| O(nlogn)| O(1)|
