Merge pull request soapyigu#361 from soapyigu/String

soapyigu · web-flow · commit adfb981f63e4 · 2022-10-05T20:35:21.000-07:00
String
diff --git a/DP/LongestIncreasingSubsequence.swift b/DP/LongestIncreasingSubsequence.swift
@@ -6,34 +6,34 @@
 
 class LongestIncreasingSubsequence {
     func lengthOfLIS(_ nums: [Int]) -> Int {
-        guard let first = nums.first else {
-            return 0
-        }
-        
-        var ends = [first]
+        var res = [nums[0]]
         
         for i in 1..<nums.count {
-            
-            // find first greater ends number
-            var left = 0, right = ends.count 
-            
-            while left < right {
-                let mid = (right - left) / 2 + left
-                
-                if ends[mid] < nums[i] {
-                    left = mid + 1
-                } else {
-                    right = mid
-                }
-            }
-            
-            if right >= ends.count {
-                ends.append(nums[i])
+            if res.last! < nums[i] {
+                res.append(nums[i])
             } else {
-                ends[right] = nums[i]
+                res[binarySearch(res, nums[i])] = nums[i]
             }
         }
         
-        return ends.count
+        return res.count
+    }
+
+    private func binarySearch(_ num: Int, _ res: [Int]) -> Int {
+        var l = 0, r = res.count - 1
+
+        while l < r {
+            let mid = (r - l) / 2 + l
+
+            if res[mid] == num {
+                return mid
+            } else if res[mid] > num {
+                r = mid
+            } else {
+                l = mid + 1
+            }
+        }
+
+        return l
     }
-}
+}
diff --git a/DP/MinimumPathSum.swift b/DP/MinimumPathSum.swift
@@ -6,27 +6,23 @@
 
 class MinimumPathSum {
     func minPathSum(_ grid: [[Int]]) -> Int {
-        guard grid.count != 0 && grid[0].count != 0 else{
-            return 0
-        }
-    
         let m = grid.count, n = grid[0].count
-        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
-        
+        var dp = grid
+
         for i in 0..<m {
             for j in 0..<n {
-                if i == 0 && j == 0{
+                if i == 0 && j == 0 {
                     dp[i][j] = grid[i][j]
                 } else if i == 0 {
-                    dp[i][j] = dp[i][j - 1] + grid[i][j]
+                    dp[i][j] += dp[i][j - 1]
                 } else if j == 0 {
-                    dp[i][j] = dp[i - 1][j] + grid[i][j]
+                    dp[i][j] += dp[i - 1][j]
                 } else {
-                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
+                    dp[i][j] += min(dp[i - 1][j], dp[i][j - 1])
                 }
             }
         }
-        
+
         return dp[m - 1][n - 1]
     }
-}
+}
diff --git a/String/GroupAnagrams.swift b/String/GroupAnagrams.swift
@@ -8,14 +8,6 @@
 
 class GroupAnagrams {
     func groupAnagrams(_ strs: [String]) -> [[String]] {
-        var sortedStrToStrs = [String: [String]]()
-  
-        for str in strs {
-            let sortedStr = String(str.sorted())
-            
-            sortedStrToStrs[sortedStr, default: []].append(str)
-        }
-        
-        return Array(sortedStrToStrs.values)
+        return Array(Dictionary(strs.map { (String($0.sorted()), [$0]) }, uniquingKeysWith: +).values)
     }
 }
