• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1071.字符串的最大公因子|GreatestCommonDivisorofStrings

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

For strings S and T, we say "T divides S" if and only if S = T + ... + T  (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides str2.

Example 1:

Input: str1 = 

Example 2:

Input: str1 = 

Example 3:

Input: str1 =  

Note:

  1. 1 <= str1.length <= 1000
  2. 1 <= str2.length <= 1000
  3. str1[i] and str2[i] are English uppercase letters.

对于字符串 S 和 T,只有在 S = T + ... + TT 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。

返回字符串 X,要求满足 X 能除尽 str1 且 X 能除尽 str2

示例 1:

输入:str1 = "ABCABC", str2 = "ABC"
输出:"ABC"

示例 2:

输入:str1 = "ABABAB", str2 = "ABAB"
输出:"AB"

示例 3:

输入:str1 = "LEET", str2 = "CODE"
输出:"" 

提示:

  1. 1 <= str1.length <= 1000
  2. 1 <= str2.length <= 1000
  3. str1[i] 和 str2[i] 为大写英文字母 

Runtime: 12 ms
Memory Usage: 21.1 MB
 1 class Solution {
 2     func gcdOfStrings(_ str1: String, _ str2: String) -> String {
 3         var str1 = str1
 4         var str2 = str2
 5         let arrStr1:[Character] = Array(str1)
 6         let arrStr2:[Character] = Array(str2)
 7         var n:Int = str1.count
 8         var m:Int = str2.count
 9 
10         for i in stride(from:n,to:0,by:-1)
11         {
12             if (n % i != 0) || (m % i != 0) {continue}
13             var flag:Bool = false
14             for j in 0..<m
15             {
16                 if arrStr2[j] != arrStr1[j % i]
17                 {
18                     flag = true
19                     break
20                 }
21             }
22             if flag {continue}
23             for j in 0..<n
24             {
25                 if arrStr1[j] != arrStr1[j % i]
26                 {
27                     flag = true
28                     break
29                 }
30             }
31             if flag {continue}
32             return str1.subString(0, i)
33         }
34         return String()
35     }
36 }
37 
38 extension String {
39     // 截取字符串:指定索引和字符数
40     // - begin: 开始截取处索引
41     // - count: 截取的字符数量
42     func subString(_ begin:Int,_ count:Int) -> String {
43         let start = self.index(self.startIndex, offsetBy: max(0, begin))
44         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
45         return String(self[start..<end])
46     }
47 }

56ms

 

 1 class Solution {
 2     func gcdOfStrings(_ str1: String, _ str2: String) -> String {
 3         let shorterStr: String
 4         let longerStr: String
 5         if str1.count > str2.count {
 6             longerStr = str1
 7             shorterStr = str2
 8         } else {
 9             longerStr = str2
10             shorterStr = str1
11         }
12         
13         for i in stride(from: shorterStr.count, to: 1, by: -1) where shorterStr.count % i == 0 && longerStr.count % i == 0 {
14             let range = shorterStr.startIndex..<shorterStr.index(shorterStr.startIndex, offsetBy: i)
15             let t = String(shorterStr[range])
16             guard shorterStr == String(repeating: t, count: shorterStr.count / i) else { continue }
17             guard longerStr == String(repeating: t, count: longerStr.count / i) else { continue }
18             return t
19         }
20         return ""
21     }
22 }

120ms

 1 class Solution {
 2   func gcdOfStrings(_ str1: String, _ str2: String) -> String {
 3     let (long, short) = str1.count > str2.count ? (str1, str2) : (str2, str1)
 4     let common = long.commonPrefix(with: short)
 5     var mu = [Substring]()
 6     for i in 1...short.count {
 7       if short.count % i == 0 {
 8         mu.append(short.prefix(short.count / i))
 9       }
10     }
11     for m in mu {
12       let s = String(m)
13       if long == String(repeating: s, count: long.count/s.count) &&
14         short == String(repeating: s, count: short.count/s.count) {
15         return s
16       }
17     }
18     return ""
19   }
20 }

184ms

 1 class Solution {
 2   func gcdOfStrings(_ str1: String, _ str2: String) -> String {
 3     let shortestString = str1 > str2 ? str2 : str1
 4     let longestString = str1 <= str2 ? str2 : str1
 5     print(shortestString)
 6     guard longestString.range(of: shortestString) != nil else { return "" }
 7     if longestString.count % shortestString.count == 0 {
 8       let timesGreater = longestString.count / shortestString.count
 9       return isRepeatative(substring: shortestString, in: longestString, times: timesGreater) ? shortestString : ""
10     } else {
11       let substrs = getSubstring(shortestString)
12       var longestSubstring = ""
13       for substr in substrs {
14         if longestString.count % substr.count == 0 {
15           let times = longestString.count / substr.count
16           if isRepeatative(substring: substr, in: longestString, times: times) && substr.count > longestSubstring.count {
17             longestSubstring = substr
18           }
19         }
20       }
21       return longestSubstring
22     }
23   }
24 
25   func isRepeatative(substring: String, in string: String, times: Int) -> Bool {
26     var str = ""
27     for _ in 0..<times {
28       str.append(substring)
29     }
30     return string == str
31   }
32 
33   func getSubstring(_ string: String) -> [String] {
34     let startIndex = string.startIndex
35     var substrings = [string]
36     for i in 2..<string.count {
37       let stopIndex = String.Index.init(encodedOffset: string.count / i)
38       let substring = String(string[startIndex..<stopIndex])
39       if isRepeatative(substring: substring, in: string, times: i) {
40         substrings.append(substring)
41       }
42     }
43     return substrings
44   }
45 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
OC与swift混编(桥接)发布时间:2022-07-13
下一篇:
1.5 Swift的表达式Expressions [Swift原创教程]发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap