leetcode 1071. Greatest Common Divisor of Strings（字符串的最大公约数）

For two strings s and t, we say “t divides s” if and only if s = t + … + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example 1:

Input: str1 = “ABCABC”, str2 = “ABC”
Output: “ABC”

Example 2:

Input: str1 = “ABABAB”, str2 = “ABAB”
Output: “AB”

Example 3:

Input: str1 = “LEET”, str2 = “CODE”
Output: “”

字符串t 能整除字符串 s 表示 s = t + … + t, 即多个t 能拼接成 s.
求s 和 t 的最大公约数字符串。

思路

这是个求最大公约数gcd的问题
回忆一下求两个数a,b 的最大公约数 gcd(a,b) = (b == 0 ? a : gcd(b, a%b).

如果 s1 和 s2 中都只有一种字母比如 s1 = AAAA, s2 = AA
那么公约数可以有A, AA, 其实就是gcd(s1.length, s2.length) = gcd(4, 2) = 2
最大公约数的长度是2 也就是AA

那如果有多个字母呢其实也是一样的前提是它们要有公约数
如何判断是不是有公约数
如果有那么s1 和 s2 都可以用公约数拼接而成s1 和 s2谁在前谁在后都可以整除公约数且整除的结果是一样的。
即 s1 + s2 == s2 + s1 时它们有公约数.

只要有公约数就可以用gcd(s1.length, s2.length)来求公约数的长度然后根据长度取出子字符串即为最大公约数。

    public String gcdOfStrings(String str1, String str2) {
        if(!(str1 + str2).equals(str2 + str1)) return "";
        
        int len = gcd(str1.length(), str2.length());
        return str1.substring(0,len);
    }

    int gcd(int a, int b) {
        return (b == 0 ? a : gcd(b, a % b));
    }