[Swift]LeetCode686.重复叠加字符串匹配|RepeatedStringMatch

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

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

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

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

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

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

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.

给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。

举个例子，A = "abcd"，B = "cdabcdab"。

答案为 3，因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。

注意:

A 与 B 字符串的长度在1和10000区间范围内。

16ms

 1 class Solution {
 2   func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3     var arrA: [UInt32] = []
 4     var arrB: [UInt32] = []
 5     var setA: Set<UInt32> = []
 6     
 7     for char in A.unicodeScalars {
 8       arrA.append(char.value)
 9       setA.insert(char.value)
10     }
11     
12     for char in B.unicodeScalars {
13       if !setA.contains(char.value) {
14         return -1
15       }
16       arrB.append(char.value)
17     }
18     
19     for i in 0..<arrA.count {
20       if arrA[i] == arrB[0] {
21         var times = 1
22         var indexI = i
23         var j = 0
24         while j < arrB.count && arrA[indexI] == arrB[j] {
25           indexI += 1
26           j += 1
27           if j < arrB.count && indexI >= arrA.count {
28             indexI = 0
29             times += 1
30           }
31         }
32         
33         if j == arrB.count {
34           return times
35         }
36       }
37     }
38     
39     return -1
40   }
41 }

24ms

 1 import Foundation
 2 
 3 class Solution {
 4     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 5         if !Set(B).isSubset(of: Set(A)) {
 6             return -1
 7         }
 8         
 9         var s = String(repeating: A, count: B.count/A.count)
10         repeat {
11             if s.contains(B) {
12                 return s.count/A.count
13             } else {
14                 s += A
15             }
16         } while (s.count < B.count + 2*A.count)
17         return -1
18     }
19 }

1372ms

 1 class Solution {
 2     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3 
 4         var setA = Set(Array(A))
 5         var setB = Set(Array(B))
 6         
 7         if !setB.isSubset(of:setA) {
 8             return -1
 9         }
10         
11         
12         
13         var string = A
14         var count = 1
15         while string.count < B.count {
16             string.append(A)
17             count += 1
18         }
19         
20         if string.contains(B) {
21             return count
22         }
23         
24         string.append(A)
25         
26         if string.contains(B) {
27             return count + 1
28         }
29         
30         return -1
31     }
32 }

1776ms

 1 class Solution {
 2     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3         if A.count == 0 || B.count == 0 {
 4             return -1
 5         }
 6         
 7         var setB = Set(B)
 8         var setA = Set(A)
 9         
10         if !setB.isSubset(of: setA) {
11             return -1
12         }
13         
14         var string = A
15         var count = 1
16         while string.count < B.count {
17             string.append(A)
18             count += 1
19         }
20         
21         if string.contains(B) {
22             return count
23         }
24         
25         string.append(A)
26         
27         if string.contains(B) {
28             return count + 1
29         }
30         
31         return -1
32     }
33 }

1848ms

 1 class Solution {
 2     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3         if A.isEmpty || B.isEmpty {
 4             return 0
 5         }
 6 
 7         let A = Array(A)
 8         let B = Array(B)
 9         var result = Int.max
10         for start in 0..<A.count {
11             var c = 0
12             var i = start
13             var j = 0
14             while j < B.count {
15                 if i == A.count {
16                     c += 1
17                     i = 0
18                 }
19                 if A[i] != B[j] {
20                     break
21                 }
22                 i += 1
23                 j += 1
24             }
25             if j == B.count {
26                 result = min(result, c + 1)
27             }
28         }
29         return result == Int.max ? -1 : result
30     }
31 }

Runtime: 2116 ms

Memory Usage: 19.6 MB

 1 class Solution {
 2     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3         var m:Int = A.count
 4         var n:Int = B.count
 5         var arrA:[Character] = Array(A)
 6         var arrB:[Character] = Array(B)
 7         for i in 0..<m
 8         {
 9             var j:Int = 0
10             while (j < n && arrA[(i + j) % m] == arrB[j])
11             {
12                 j += 1
13             }
14             if j == n
15             {
16                 return (i + j - 1) / m + 1
17             }
18         }
19         return -1
20     }
21 }

2392ms

 1 class Solution {
 2     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3         let arrayA = Array(A), arrayB = Array(B)
 4         guard let firstB = arrayB.first else { return -1 }
 5         var indexAs = arrayA.indices.filter { arrayA[$0] == firstB }
 6         guard indexAs.count > 0 else { return -1 }
 7         
 8         var minRepeatCount = -1
 9         for indexA in indexAs {
10             var indexA = indexA
11             var repeatCount = 1
12             for indexB in arrayB.indices {
13                 if arrayB[indexB] != arrayA[indexA] {
14                     repeatCount = -1
15                     break
16                 }
17 
18                 // important
19                 if indexB == arrayB.count - 1 {
20                     break
21                 }
22 
23                 if indexA == arrayA.count - 1 {
24                     repeatCount += 1
25                     indexA = 0
26                 } else {
27                     indexA += 1
28                 }
29             }
30             
31             if repeatCount != -1 {
32                 if minRepeatCount == -1 {
33                     minRepeatCount = repeatCount
34                 } else {
35                     minRepeatCount = min(minRepeatCount, repeatCount)
36                 }
37             }
38         }
39         return minRepeatCount
40     }
41 }

2572ms

 1 class Solution {
 2     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3         let aChars = A.unicodeScalars.map { $0.value }
 4         let bChars = B.unicodeScalars.map { $0.value }
 5         guard bChars.count > 0 else {
 6             return -1
 7         }
 8 
 9         var startComparing = false
10         var i = 0
11         var j = 0
12         while true {
13             if i >= aChars.count, !startComparing {
14                 break
15             }
16             if j >= bChars.count {
17                 break
18             }
19             if aChars[i % aChars.count] != bChars[j] {
20                 if startComparing {
21                     startComparing = false
22                     i -= j
23                     j = 0
24                 }
25                 i += 1
26                 continue
27             } else {
28                 if !startComparing {
29                     startComparing = true
30                 }
31                 i += 1 
32                 j += 1
33                 continue
34             }
35         }
36         return startComparing ? Int(ceil(Double(i)/Double(aChars.count))) : -1
37     }
38 }

3956ms

 1 class Solution {
 2     func repeatedStringMatch(_ A: String, _ B: String) -> Int {
 3         if A.isEmpty { return -1 }
 4         if A == B || A.contains(B) { return 1 }
 5         var i = 1
 6         var newString = A
 7         
 8         if Set(A).count != Set(B).count { return -1 }
 9         
10         var limit = A.count > B.count ? 2 : (B.count / A.count) + 1
11         
12         while i <= limit {
13             i += 1
14             newString += A
15             if newString.count >= B.count && newString.range(of: B) != nil {
16                 return i
17             }
18         }
19         return -1
20     }
21 }