大佬教程收集整理的这篇文章主要介绍了[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".
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@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 var arrA: [UInt32] =@H_616_53@ [] 4 var arrB: [UInt32] =@H_616_53@ [] 5 var setA: Set<UInt32> =@H_616_53@ [] 6 7 for char in@H_616_53@ A.unicodeScalars { 8 arrA.append(char@H_616_53@.value) 9 setA.insert(char@H_616_53@.value) 10 @H_616_53@ } 11 12 for char in@H_616_53@ B.unicodeScalars { 13 if !setA.contains(char@H_616_53@.value) { 14 return -1 15 @H_616_53@ } 16 arrB.append(char@H_616_53@.value) 17 @H_616_53@ } 18 19 for i in 0..<@H_616_53@arrA.count { 20 if arrA[i] == arrB[0@H_616_53@] { 21 var times = 1 22 var indexI =@H_616_53@ i 23 var j = 0 24 while j < arrB.count && arrA[indexI] ==@H_616_53@ arrB[j] { 25 indexI += 1 26 j += 1 27 if j < arrB.count && indexI >=@H_616_53@ arrA.count { 28 indexI = 0 29 times += 1 30 @H_616_53@ } 31 @H_616_53@ } 32 33 if j ==@H_616_53@ arrB.count { 34 return@H_616_53@ times 35 @H_616_53@ } 36 @H_616_53@ } 37 @H_616_53@ } 38 39 return -1 40 @H_616_53@ } 41 }
24ms
1 @H_616_53@import Foundation 2 3 class@H_616_53@ Solution { 4 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 5 if !@H_616_53@Set(B).isSubset(of: Set(A)) { 6 return -1 7 @H_616_53@ } 8 9 var s = String(repeaTing: A,count: B.count/@H_616_53@A.count) 10 @H_616_53@ repeat { 11 if@H_616_53@ s.contains(B) { 12 return s.count/@H_616_53@A.count 13 } else@H_616_53@ { 14 s +=@H_616_53@ A 15 @H_616_53@ } 16 } while (s.count < B.count + 2*@H_616_53@A.count) 17 return -1 18 @H_616_53@ } 19 }
1372ms
1 class@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 4 var setA =@H_616_53@ Set(Array(A)) 5 var setB =@H_616_53@ Set(Array(B)) 6 7 if !@H_616_53@setB.isSubset(of:setA) { 8 return -1 9 @H_616_53@ } 10 11 12 13 var String =@H_616_53@ A 14 var count = 1 15 while String.count <@H_616_53@ B.count { 16 String@H_616_53@.append(A) 17 count += 1 18 @H_616_53@ } 19 20 if String@H_616_53@.contains(B) { 21 return@H_616_53@ count 22 @H_616_53@ } 23 24 String@H_616_53@.append(A) 25 26 if String@H_616_53@.contains(B) { 27 return count + 1 28 @H_616_53@ } 29 30 return -1 31 @H_616_53@ } 32 }
1776ms
1 class@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 if A.count == 0 || B.count == 0@H_616_53@ { 4 return -1 5 @H_616_53@ } 6 7 var setB =@H_616_53@ Set(B) 8 var setA =@H_616_53@ Set(A) 9 10 if !@H_616_53@setB.isSubset(of: setA) { 11 return -1 12 @H_616_53@ } 13 14 var String =@H_616_53@ A 15 var count = 1 16 while String.count <@H_616_53@ B.count { 17 String@H_616_53@.append(A) 18 count += 1 19 @H_616_53@ } 20 21 if String@H_616_53@.contains(B) { 22 return@H_616_53@ count 23 @H_616_53@ } 24 25 String@H_616_53@.append(A) 26 27 if String@H_616_53@.contains(B) { 28 return count + 1 29 @H_616_53@ } 30 31 return -1 32 @H_616_53@ } 33 }
1848ms
1 class@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 if A.isEmpty ||@H_616_53@ B.isEmpty { 4 return 0 5 @H_616_53@ } 6 7 let A =@H_616_53@ Array(A) 8 let B =@H_616_53@ Array(B) 9 var result =@H_616_53@ Int.max 10 for start in 0..<@H_616_53@A.count { 11 var c = 0 12 var i =@H_616_53@ start 13 var j = 0 14 while j <@H_616_53@ B.count { 15 if i ==@H_616_53@ A.count { 16 c += 1 17 i = 0 18 @H_616_53@ } 19 if A[i] !=@H_616_53@ B[j] { 20 break 21 @H_616_53@ } 22 i += 1 23 j += 1 24 @H_616_53@ } 25 if j ==@H_616_53@ B.count { 26 result = min(result,c + 1@H_616_53@) 27 @H_616_53@ } 28 @H_616_53@ } 29 return result == Int.max ? -1@H_616_53@ : result 30 @H_616_53@ } 31 }
1 class@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 var m:Int =@H_616_53@ A.count 4 var n:Int =@H_616_53@ B.count 5 var arrA:[Character] =@H_616_53@ Array(A) 6 var arrB:[Character] =@H_616_53@ Array(B) 7 for i in 0..<@H_616_53@m 8 @H_616_53@ { 9 var j:Int = 0 10 while (j < n && arrA[(i + j) % m] ==@H_616_53@ arrB[j]) 11 @H_616_53@ { 12 j += 1 13 @H_616_53@ } 14 if j ==@H_616_53@ n 15 @H_616_53@ { 16 return (i + j - 1) / m + 1 17 @H_616_53@ } 18 @H_616_53@ } 19 return -1 20 @H_616_53@ } 21 }
2392ms
1 class@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 let arrayA = Array(A),arrayB =@H_616_53@ Array(B) 4 guard let firstB = arrayB.first else { return -1@H_616_53@ } 5 var indexAs = arrayA.inDices.filter { arrayA[$0] ==@H_616_53@ firstB } 6 guard indexAs.count > 0 else { return -1@H_616_53@ } 7 8 var minRepeatCount = -1 9 for indexA in@H_616_53@ indexAs { 10 var indexA =@H_616_53@ indexA 11 var repeatCount = 1 12 for indexB in@H_616_53@ arrayB.inDices { 13 if arrayB[indexB] !=@H_616_53@ arrayA[indexA] { 14 repeatCount = -1 15 break 16 @H_616_53@ } 17 18 // important 19 if indexB == arrayB.count - 1@H_616_53@ { 20 break 21 @H_616_53@ } 22 23 if indexA == arrayA.count - 1@H_616_53@ { 24 repeatCount += 1 25 indexA = 0 26 } else@H_616_53@ { 27 indexA += 1 28 @H_616_53@ } 29 @H_616_53@ } 30 31 if repeatCount != -1@H_616_53@ { 32 if minRepeatCount == -1@H_616_53@ { 33 minRepeatCount =@H_616_53@ repeatCount 34 } else@H_616_53@ { 35 minRepeatCount =@H_616_53@ min(minRepeatCount,repeatCount) 36 @H_616_53@ } 37 @H_616_53@ } 38 @H_616_53@ } 39 return@H_616_53@ minRepeatCount 40 @H_616_53@ } 41 }
2572ms
1 class@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 let aChars = A.unicodeScalars.map { $0@H_616_53@.value } 4 let bChars = B.unicodeScalars.map { $0@H_616_53@.value } 5 guard bChars.count > 0 else@H_616_53@ { 6 return -1 7 @H_616_53@ } 8 9 var startComparing = false 10 var i = 0 11 var j = 0 12 while true@H_616_53@ { 13 if i >= aChars.count,!@H_616_53@startComparing { 14 break 15 @H_616_53@ } 16 if j >=@H_616_53@ bChars.count { 17 break 18 @H_616_53@ } 19 if aChars[i % aChars.count] !=@H_616_53@ bChars[j] { 20 if@H_616_53@ startComparing { 21 startComparing = false 22 i -=@H_616_53@ j 23 j = 0 24 @H_616_53@ } 25 i += 1 26 conTinue 27 } else@H_616_53@ { 28 if !@H_616_53@startComparing { 29 startComparing = true 30 @H_616_53@ } 31 i += 1 32 j += 1 33 conTinue 34 @H_616_53@ } 35 @H_616_53@ } 36 return startComparing ? Int(ceil(Double(i)/Double(aChars.count))) : -1 37 @H_616_53@ } 38 }
3956ms
1 class@H_616_53@ Solution { 2 func repeatedStringMatch(_ A: String,_ B: String) ->@H_616_53@ Int { 3 if A.isEmpty { return -1@H_616_53@ } 4 if A == B || A.contains(B) { return 1@H_616_53@ } 5 var i = 1 6 var newString =@H_616_53@ A 7 8 if Set(A).count != Set(B).count { return -1@H_616_53@ } 9 10 var limit = A.count > B.count ? 2 : (B.count / A.count) + 1 11 12 while i <=@H_616_53@ limit { 13 i += 1 14 newString +=@H_616_53@ A 15 if newString.count >= B.count && newString.range(of: B) !=@H_616_53@ nil { 16 return@H_616_53@ i 17 @H_616_53@ } 18 @H_616_53@ } 19 return -1 20 @H_616_53@ } 21 }
以上是大佬教程为你收集整理的[Swift]LeetCode686. 重复叠加字符串匹配 | Repeated String Match全部内容,希望文章能够帮你解决[Swift]LeetCode686. 重复叠加字符串匹配 | Repeated String Match所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。