[String] Optimize the code style of Word Pattern and add a new solution to Find Duplicate File in System

soapyigu · soapyigu · commit 42aebadfa1b5 · 2018-06-18T23:08:14.000-07:00
diff --git a/README.md b/README.md
@@ -28,7 +28,7 @@
 * [Microsoft](#microsoft)
 
 ## Progress
-[Problem Status](#problem-status) shows the latest progress to all 800+ questions. Currently we have 255 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them. Thank you for great contributions from [CharleneJiang](https://github.com/CharleneJiang), [ReadmeCritic](https://github.com/ReadmeCritic), [demonkoo](https://github.com/demonkoo), [DaiYue](https://github.com/DaiYue), [Quaggie](https://github.com/Quaggie) and [jindulys](https://github.com/jindulys).
+[Problem Status](#problem-status) shows the latest progress to all 800+ questions. Currently we have 256 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them. Thank you for great contributions from [CharleneJiang](https://github.com/CharleneJiang), [ReadmeCritic](https://github.com/ReadmeCritic), [demonkoo](https://github.com/demonkoo), [DaiYue](https://github.com/DaiYue), [Quaggie](https://github.com/Quaggie) and [jindulys](https://github.com/jindulys).
 
 
 ## Array
@@ -99,6 +99,7 @@
 [Valid Anagram](https://leetcode.com/problems/valid-anagram/)| [Swift](./String/ValidAnagram.swift)| Easy| O(nlogn)| O(1)|
 [Ransom Note](https://leetcode.com/problems/ransom-note/)| [Swift](./String/RansomNote.swift)| Easy| O(n)| O(n)|
 [Group Anagrams](https://leetcode.com/problems/anagrams/)| [Swift](./String/GroupAnagrams.swift)| Medium| O(nmlogm + nlogn)| O(n)
+[Find Duplicate File in System](https://leetcode.com/problems/find-duplicate-file-in-system/)| [Swift](./String/FindDuplicateFileInSystem.swift)| Medium| O(nm)| O(n)
 [Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)| [Swift](./String/LongestCommonPrefix.swift)| Easy| O(nm)| O(m)|
 [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)| [Swift](./String/LongestSubstringWithoutRepeatingCharacters.swift)| Medium| O(n)| O(n)|
 [One Edit Distance](https://leetcode.com/problems/one-edit-distance/)| [Swift](./String/OneEditDistance.swift)| Medium| O(n)| O(n)|
diff --git a/String/FindDuplicateFileInSystem.swift b/String/FindDuplicateFileInSystem.swift
@@ -0,0 +1,36 @@
+/**
+ * Question Link: https://leetcode.com/problems/find-duplicate-file-in-system/
+ * Primary idea: Iterate the paths array and categories paths with the same content
+ *
+ * Time Complexity: O(nm), n stands for number of paths, m stands for file number in a path
+ *                  Space Complexity: O(n)
+ */
+
+class FindDuplicateFileInSystem {
+    func findDuplicate(_ paths: [String]) -> [[String]] {
+        var contentToFiles = [String: [String]]()
+    
+        for path in paths {
+            let params = path.split(separator: " ")
+        
+            guard let dir = params.first else {
+                continue
+            }
+        
+            for i in 1..<params.count {
+                let fileParams = params[i].split(separator: "(")
+            
+                guard let fileName = fileParams.first, let fileContentWithExtraInfo = fileParams.last else {
+                    continue
+                }
+            
+                let fileContent = String(describing: fileContentWithExtraInfo.dropLast())
+                let filePath = String(describing: dir) + "/" + String(describing: fileName)
+            
+                contentToFiles[fileContent] = contentToFiles[fileContent, default: []] + [filePath]
+            }
+        }
+    
+        return contentToFiles.values.filter { $0.count >= 2 }
+    }
+}
diff --git a/String/WordPattern.swift b/String/WordPattern.swift
@@ -5,25 +5,24 @@
  */
 
 class WordPattern {
-    func wordPattern(pattern: String, _ str: String) -> Bool {
-        var wordDict = [String: Character]()
-        var charDict = [Character: String]()
-        let strs = str.characters.split{$0 == " "}.map(String.init)
-        let patterns = [Character](pattern.characters)
+    func wordPattern(_ pattern: String, _ str: String) -> Bool {
+        let strs = str.split(separator: " ").map(String.init)
         
-        guard patterns.count == strs.count else {
+        guard pattern.count == strs.count else {
             return false
         }
         
-        for i in 0..<strs.count {
-            let currentWord = strs[i]
-            let currentChar = patterns[i]
+        var patternToWord = [Character: String]()
+        var wordToPattern = [String: Character]()
         
-            if wordDict[currentWord] == nil && charDict[currentChar] == nil{
-                wordDict[currentWord] = currentChar
-                charDict[currentChar] = currentWord
+        for (i, char) in pattern.enumerated() {
+            let word = strs[i]
+            
+            if patternToWord[char] == nil && wordToPattern[word] == nil {
+                wordToPattern[word] = char
+                patternToWord[char] = word
             } else {
-                if wordDict[currentWord] != currentChar {
+                if patternToWord[char] != word || wordToPattern[word] != char {
                     return false
                 }
             }
