Merge pull request soapyigu#235 from iHackSubhodip/master

soapyigu · web-flow · commit b2e76786c409 · 2019-05-11T12:40:16.000-07:00
Optimize solution to Decode String &amp; LRU Cache
diff --git a/Design/LRUCache.swift b/Design/LRUCache.swift
@@ -0,0 +1,75 @@
+/**
+ * Question Link: https://leetcode.com/problems/lru-cache/
+ * Primary idea: Use Doubly linked list and hash table to build the LRU cache.
+ * Time Complexity: O(1), Space Complexity: O(n)
+ *
+ */
+
+class DoublyLinkedList{
+    var key: Int
+    var value: Int
+    var previous: DoublyLinkedList?
+    var next: DoublyLinkedList?
+    var hashValue: Int
+    
+    init(_ key: Int, _ value: Int) {
+        self.key = key
+        self.value = value
+        self.hashValue = key
+    }
+}
+
+class LRUCache{
+    var maxCapacity: Int
+    var head: DoublyLinkedList
+    var tail: DoublyLinkedList
+    var cache: [Int: DoublyLinkedList]
+    
+    init(_ maxCapacity: Int) {
+        self.maxCapacity = maxCapacity
+        self.cache = [Int: DoublyLinkedList]()
+        self.head = DoublyLinkedList(Int.min, Int.min)
+        self.tail = DoublyLinkedList(Int.max, Int.max)
+        self.head.next = self.tail
+        self.tail.previous = self.head
+    }
+    
+    func add(_ node: DoublyLinkedList){
+        let next = head.next
+        head.next = node
+        node.previous = head
+        node.next = next
+        next?.previous = node
+    }
+    
+    func remove(_ node: DoublyLinkedList){
+        let previous = node.previous
+        let next = node.next
+        previous?.next = next
+        next?.previous = previous
+    }
+    
+    func get(_ key: Int) -> Int{
+        if let node = cache[key]{
+            remove(node)
+            add(node)
+            return node.value
+        }
+        return -1
+    }
+    
+    func put(_ key: Int, _ value: Int){
+        if let node = cache[key]{
+            remove(node)
+            cache.removeValue(forKey: key)
+        }else if cache.keys.count >= maxCapacity{
+            if let leastNode = tail.previous{
+                remove(leastNode)
+                cache.removeValue(forKey: leastNode.key)
+            }
+        }
+        let newNode = DoublyLinkedList(key, value)
+        cache[key] = newNode
+        add(newNode)
+    }
+}
diff --git a/README.md b/README.md
@@ -157,6 +157,7 @@
 [Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)| [Swift](./Stack/PreorderTraversal.swift)| Medium| O(n)| O(n)|
 [Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)| [Swift](./Stack/InorderTraversal.swift)| Medium| O(n)| O(n)|
 [Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)| [Swift](./Stack/PostorderTraversal.swift)| Hard| O(n)| O(n)|
+[Decode String](https://leetcode.com/problems/decode-string/)| [Swift](./Stack/DecodeString.swift)| Medium| O(n)| O(n)|
 
 
 ## Tree
@@ -350,6 +351,11 @@
 [Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/)| [Swift](./UnionFind/GraphValidTree.swift)| Medium| O(nlogn)| O(n)|
 [Number of Islands II](https://leetcode.com/problems/number-of-islands-ii/)| [Swift](./UnionFind/NumberIslandsII.swift)| Hard| O(klogmn)| O(mn)|
 
+## Design
+| Title | Solution | Difficulty | Time | Space |
+| ----- | -------- | ---------- | ---- | ----- |
+[LRU Cache](https://leetcode.com/problems/lru-cache/)| [Swift](./Design/LRUCache.swift)| Hard| O(1)| O(n)|
+
 ## Google
 | Title | Solution | Difficulty | Frequency |
 | ----- | -------- | ---------- | --------- |
diff --git a/Stack/DecodeString.swift b/Stack/DecodeString.swift
@@ -0,0 +1,52 @@
+/**
+ * Question Link: https://leetcode.com/problems/decode-string/
+ * Primary idea: Primary idea is to maintain two stacks[i.e. countStack and characterStack].
+ *               Traverse the given string and process the elements into the respective stacks, and accordingly update the result.
+ * Time Complexity: O(n), Space Complexity: O(n)
+ * 
+ */
+
+
+class Solution {
+    func decodeString(_ s: String) -> String {
+        var result = ""
+        var countStack = [Int]()
+        var characterStack = [String]()
+        let allowedDigits = Set(["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"])
+        var arrayString = Array(s), i = 0
+        
+        while i < arrayString.count{
+            
+            if allowedDigits.contains(String(arrayString[i])){
+                
+                var count = 0
+                while allowedDigits.contains(String(arrayString[i])){
+                    count = 10 * count + Int(String(arrayString[i]))!
+                    i += 1
+                }
+                countStack.append(count)
+            }else if arrayString[i] == "["{
+                
+                characterStack.append(result)
+                result = ""
+                i += 1
+            }else if arrayString[i] == "]"{
+                
+                if var temp = characterStack.popLast(), let repeatTime = countStack.popLast(){
+                    
+                    for _ in 0..<repeatTime{
+                        temp.append(result)
+                    }
+                    result = temp
+                }
+                i += 1
+            }else{
+                
+                result.append(arrayString[i])
+                i += 1
+            }
+        }
+        
+        return result
+    }
+}
