https://leetcode.com/problems/interleaving-string/
刚开始都没看懂题目,什么叫做交织?就是将s1和s2分解,但是不能打乱顺序,比如第一个Example
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 我们将s1分解成aa, bc, c然后将s2分解成dbbc, a。依靠aa+dbbc+bc+a+c就能组合成s3,而Example2不行,返回False。
题目第一次看见确实挺难的,思考了解决方案都是各种超过了时间限时,不管是循环还是递归,看了答案,下面是答案中的最优解决方案,可能使用String.Index过程中还有一点限制速度的地方,内存使用确实达到了100%

class Solution {
    func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
        guard s1.count + s2.count == s3.count else { return false }
        var dp = Array<Bool>(repeating: false, count: s2.count + 1)
        for i in 0...s1.count {
            for j in 0...s2.count {
                if i == 0 && j == 0 {
                    dp[j] = true
                } else if i == 0 {
                    dp[j] = dp[j - 1] && s2[j - 1] == s3[i + j - 1]
                } else if j == 0 {
                    dp[j] = dp[j] && s1[i - 1] == s3[i + j - 1]
                } else {
                    dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] == s3[i + j - 1])
                }
            }
        }
        return dp[s2.count]
    }
}

extension String {
    subscript(_ i: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: i)]
    }
}

Runtime: 16 ms, faster than 91.67% of Swift online submissions for Interleaving String.
Memory Usage: 18.8 MB, less than 100.00% of Swift online submissions for Interleaving String.