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

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

原作者: [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 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] and str2[i] are English uppercase letters.

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 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 <= str1.length <= 1000
1 <= str2.length <= 1000
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 }