Merge pull request soapyigu#366 from soapyigu/Array

soapyigu · web-flow · commit a440c74bcd7c · 2022-10-09T15:17:58.000-07:00
Array
diff --git a/Array/NextPalindromeUsingSameDigits.swift b/Array/NextPalindromeUsingSameDigits.swift
@@ -0,0 +1,56 @@
+/**
+ * Question Link: https://leetcode.com/problems/next-palindrome-using-same-digits/
+ * Primary idea: Figure out the first half's next permutation, then double it to the result.
+ *
+ * Time Complexity: O(n), Space Complexity: O(1)
+ *
+ */
+
+class NextPalindromeUsingSameDigits {
+    func nextPalindrome(_ num: String) -> String {
+        let num = Array(num)
+        var firstHalf = num[0..<num.count / 2].compactMap { Int(String($0)) }
+        
+        if num.count <= 1 || !nextPermutation(&firstHalf) {
+            return ""
+        }
+        
+        let firstHalfStr = firstHalf.map { String($0) }.joined()
+        
+        if num.count % 2 == 0 {
+            return firstHalfStr + firstHalfStr.reversed()
+        } else {
+            return firstHalfStr + String(num[num.count / 2]) + firstHalfStr.reversed()
+        }
+    }
+
+    private func nextPermutation(_ nums: inout [Int]) -> Bool {
+        var violateIdx = -1
+        
+        for i in (1..<nums.count).reversed() {
+            if nums[i] > nums[i - 1] {
+                violateIdx = i - 1
+                break
+            }
+        }
+        
+        if violateIdx == -1 {
+            nums.reverse()
+            return false
+        }
+        
+        for i in ((violateIdx + 1)..<nums.count).reversed() {
+            if nums[i] > nums[violateIdx] {
+                swap(&nums, i, violateIdx)
+                break
+            }
+        }
+        
+        nums[(violateIdx + 1)...].reverse()
+        return true
+    }
+
+    private func swap(_ nums: inout [Int], _ l: Int, _ r: Int) {
+        (nums[l], nums[r]) = (nums[r], nums[l])
+    }
+}
diff --git a/Array/NextPermutation.swift b/Array/NextPermutation.swift
@@ -9,36 +9,36 @@
 
 class NextPermutation {
     func nextPermutation(_ nums: inout [Int]) {
-        guard let violateIndex = findViolate(nums) else {
+        guard let violateIdx = findViolate(nums) else {
             nums.reverse()
             return
         }
-        
-        swap(&nums, violateIndex, findLeastGreater(nums, violateIndex))
-        nums = nums[0...violateIndex] + nums[(violateIndex + 1)...].reversed()
+
+        swap(&nums, findFirstGreater(nums, violateIdx), violateIdx)
+        nums[(violateIdx + 1)...].reverse()
+    }
+
+    private func findFirstGreater(_ nums: [Int], _ violateIdx: Int) -> Int {
+        for i in ((violateIdx + 1)..<nums.count).reversed() {
+            if nums[i] > nums[violateIdx] {
+                return i
+            }
+        }
+
+        return -1
     }
-    
-    fileprivate func findViolate(_ nums: [Int]) -> Int? {
+
+    private func findViolate(_ nums: [Int]) -> Int? {
         for i in (1..<nums.count).reversed() {
             if nums[i] > nums[i - 1] {
                 return i - 1
             }
         }
-        
+
         return nil
     }
-    
-    fileprivate func findLeastGreater(_ nums: [Int], _ violateIndex: Int) -> Int {
-        for i in (violateIndex + 1..<nums.count).reversed() {
-            if nums[i] > nums[violateIndex] {
-                return i
-            }
-        }
-        
-        fatalError()
-    }
-    
-    fileprivate func swap<T>(_ nums: inout [T], _ indexL: Int, _ indexR: Int) {
-        (nums[indexL], nums[indexR]) = (nums[indexR], nums[indexL])
+
+    private func swap(_ nums: inout [Int], _ l: Int, _ r: Int) {
+        (nums[l], nums[r]) = (nums[r], nums[l])
     }
-}
+}
