[Swift]LeetCode97.交错字符串|InterleavingString

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

12ms

 1 class Solution {
 2     func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
 3         var cache = [[Int]](repeating: [Int](repeating: -1, count: s2.count), count: s1.count)
 4         return is_Interleave(s1, 0, s2, 0, s3, 0, &cache)
 5     }
 6 
 7     fileprivate func is_Interleave(_ s1: String, _ i: Int, _ s2: String, _ j: Int, _ s3: String, _ k: Int, _ cache: inout [[Int]]) -> Bool {
 8         if i == s1.count {
 9             return s2[j..<s2.count] == s3[k..<s3.count]
10         }
11         if j == s2.count {
12             return s1[i..<s1.count] == s3[k..<s3.count]
13         }
14         if cache[i][j] >= 0 {
15             return cache[i][j] == 1 ? true : false
16         }
17 
18         var ans = false
19 
20         if (s3[k] == s1[i] && is_Interleave(s1, i + 1, s2, j, s3, k + 1, &cache)) ||
21             (s3[k] == s2[j] && is_Interleave(s1, i, s2, j + 1, s3, k + 1, &cache)) {
22             ans = true
23         }
24         cache[i][j] = ans ? 1 : 0
25 
26         return ans
27     }
28 }
29 
30 extension String {
31     subscript (i: Int) -> Character {
32         return self[index(startIndex, offsetBy: i)]
33     }
34     
35     subscript(_ range: CountableRange<Int>) -> String {
36         let idx1 = index(startIndex, offsetBy: max(0, range.lowerBound))
37         let idx2 = index(startIndex, offsetBy: min(self.count, range.upperBound))
38         return String(self[idx1..<idx2])
39     }
40 }

12ms

 1 class Solution {
 2     func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
 3         if s1.count + s2.count != s3.count {
 4             return false
 5         }
 6         var dp: [[Bool]] = Array<Array<Bool>>(repeating: Array<Bool>(repeating: false, count: s2.count+1), count: s1.count+1)
 7         for i in 0 ..< s1.count + 1{
 8             for j in 0 ..< s2.count + 1{
 9                 if i == 0 && j == 0 {
10                     dp[0][0] = true
11                 } else if i == 0 {
12                     dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1])
13                 } else if j == 0 {
14                     dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1])
15                 } else {
16                     dp[i][j] = (dp[i][j-1] && (s2[j-1] == s3[i+j-1])) || (dp[i-1][j] && (s1[i-1] == s3[i+j-1]))
17                 }
18             }
19         }
20         return dp[s1.count][s2.count]
21     }
22 }
23 
24 extension String {
25     subscript(index: Int) -> Character {
26         return self[self.index(self.startIndex, offsetBy: index)]
27     }
28 }