feat: add swift implementation to lcof2 problem: No.096 (doocs#3482)

klever34 · web-flow · commit ce1d4f87fea6 · 2024-09-03T17:35:37.000+08:00
diff --git a/lcof2/剑指 Offer II 096. 字符串交织/README.md b/lcof2/剑指 Offer II 096. 字符串交织/README.md
@@ -290,6 +290,51 @@ public class Solution {
 }
 ```
 
+#### Swift
+
+```swift
+class Solution {
+    private var memo = [String: Bool]()
+    private var s1: [Character] = []
+    private var s2: [Character] = []
+    private var s3: [Character] = []
+    private var m = 0
+    private var n = 0
+
+    func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
+        m = s1.count
+        n = s2.count
+        if m + n != s3.count {
+            return false
+        }
+        self.s1 = Array(s1)
+        self.s2 = Array(s2)
+        self.s3 = Array(s3)
+        return dfs(0, 0)
+    }
+
+    private func dfs(_ i: Int, _ j: Int) -> Bool {
+        if i >= m && j >= n {
+            return true
+        }
+        let key = "\(i),\(j)"
+        if let cached = memo[key] {
+            return cached
+        }
+        let k = i + j
+        var ans = false
+        if i < m && s1[i] == s3[k] && dfs(i + 1, j) {
+            ans = true
+        }
+        if !ans && j < n && s2[j] == s3[k] && dfs(i, j + 1) {
+            ans = true
+        }
+        memo[key] = ans
+        return ans
+    }
+}
+```
+
 <!-- tabs:end -->
 
 <!-- solution:end -->
diff --git a/lcof2/剑指 Offer II 096. 字符串交织/Solution.swift b/lcof2/剑指 Offer II 096. 字符串交织/Solution.swift
@@ -0,0 +1,40 @@
+class Solution {
+    private var memo = [String: Bool]()
+    private var s1: [Character] = []
+    private var s2: [Character] = []
+    private var s3: [Character] = []
+    private var m = 0
+    private var n = 0
+
+    func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
+        m = s1.count
+        n = s2.count
+        if m + n != s3.count {
+            return false
+        }
+        self.s1 = Array(s1)
+        self.s2 = Array(s2)
+        self.s3 = Array(s3)
+        return dfs(0, 0)
+    }
+
+    private func dfs(_ i: Int, _ j: Int) -> Bool {
+        if i >= m && j >= n {
+            return true
+        }
+        let key = "\(i),\(j)"
+        if let cached = memo[key] {
+            return cached
+        }
+        let k = i + j
+        var ans = false
+        if i < m && s1[i] == s3[k] && dfs(i + 1, j) {
+            ans = true
+        }
+        if !ans && j < n && s2[j] == s3[k] && dfs(i, j + 1) {
+            ans = true
+        }
+        memo[key] = ans
+        return ans
+    }
+}
