[Swift]LeetCode686. 重复叠加字符串匹配 | Repeated String Match

概述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". Retu @H_419_0@ @H_419_0@

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 -115       }16       arrB.append(char.value)17     }18     19     for i in 0..<arrA.count {20       if arrA[i] == arrB[0] {21         var times = 122         var indexI = i23         var j = 024         while j < arrB.count && arrA[indexI] == arrB[j] {25           indexI += 126           j += 127           if j < arrB.count && indexI >= arrA.count {28             indexI = 029             times += 130           }31         }32         33         if j == arrB.count {34           return times35         }36       }37     }38     39     return -140   }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.count13             } else {14                 s += A15             }16         } while (s.count < B.count + 2*A.count)17         return -118     }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 = A14         var count = 115         while string.count < B.count {16             string.append(A)17             count += 118         }19         20         if string.contains(B) {21             return count22         }23         24         string.append(A)25         26         if string.contains(B) {27             return count + 128         }29         30         return -131     }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 -112         }13         14         var string = A15         var count = 116         while string.count < B.count {17             string.append(A)18             count += 119         }20         21         if string.contains(B) {22             return count23         }24         25         string.append(A)26         27         if string.contains(B) {28             return count + 129         }30         31         return -132     }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.max10         for start in 0..<A.count {11             var c = 012             var i = start13             var j = 014             while j < B.count {15                 if i == A.count {16                     c += 117                     i = 018                 }19                 if A[i] != B[j] {20                     break21                 }22                 i += 123                 j += 124             }25             if j == B.count {26                 result = min(result,c + 1)27             }28         }29         return result == Int.max ? -1 : result30     }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 = 010             while (j < n && arrA[(i + j) % m] == arrB[j])11             {12                 j += 113             }14             if j == n15             {16                 return (i + j - 1) / m + 117             }18         }19         return -120     }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 = indexA11             var repeatCount = 112             for indexB in arrayB.indices {13                 if arrayB[indexB] != arrayA[indexA] {14                     repeatCount = -115                     break16                 }17 18                 // important19                 if indexB == arrayB.count - 1 {20                     break21                 }22 23                 if indexA == arrayA.count - 1 {24                     repeatCount += 125                     indexA = 026                 } else {27                     indexA += 128                 }29             }30             31             if repeatCount != -1 {32                 if minRepeatCount == -1 {33                     minRepeatCount = repeatCount34                 } else {35                     minRepeatCount = min(minRepeatCount,repeatCount)36                 }37             }38         }39         return minRepeatCount40     }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 = false10         var i = 011         var j = 012         while true {13             if i >= aChars.count,!startComparing {14                 break15             }16             if j >= bChars.count {17                 break18             }19             if aChars[i % aChars.count] != bChars[j] {20                 if startComparing {21                     startComparing = false22                     i -= j23                     j = 024                 }25                 i += 126                 continue27             } else {28                 if !startComparing {29                     startComparing = true30                 }31                 i += 1 32                 j += 133                 continue34             }35         }36         return startComparing ? Int(ceil(Double(i)/Double(aChars.count))) : -137     }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) + 111         12         while i <= limit {13             i += 114             newString += A15             if newString.count >= B.count && newString.range(of: B) != nil {16                 return i17             }18         }19         return -120     }21 }

@H_419_0@ 总结

以上是内存溢出为你收集整理的[Swift]LeetCode686. 重复叠加字符串匹配 | Repeated String Match全部内容，希望文章能够帮你解决[Swift]LeetCode686. 重复叠加字符串匹配 | Repeated String Match所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。