1071. 字符串的最大公因子

解题思路：

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func gcdOfStrings(str1 string, str2 string) string {
    n1, n2 := len(str1), len(str2)

    // 从最长的可能的子串长度开始尝试
    for i := min(n1, n2); i > 0; i-- {
        if n1%i == 0 && n2%i == 0 {
            commonSubstring := str1[:i]

            // 检查是否满足条件
            if checkDivisible(str1, commonSubstring) && checkDivisible(str2, commonSubstring) {
                return commonSubstring
            }
        }
    }

    return ""
}

// 检查字符串是否能够整除
func checkDivisible(s string, sub string) bool {
    repeats := len(s) / len(sub)
    concatenated := repeatString(sub, repeats)
    return s == concatenated
}

// 重复字符串
func repeatString(s string, count int) string {
    result := ""
    for i := 0; i < count; i++ {
        result += s
    }
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}


数学方法

辗转相除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func gcdOfStrings(str1 string, str2 string) string {
    if str1 + str2 != str2 + str1 {
        return ""
    }
    gcd := gcd(len(str1), len(str2))
    return str1[0:gcd]
}

  

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}