[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: “”

Constraints:
1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

字符串的最大公因子。

对于字符串 s 和 t，只有在 s = t + … + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/greatest-common-divisor-of-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这是一道数学题，说是求字符串的最大公因子，其实是需要先求出两个字符串长度的最大公约数然后得到子串。其中求最大公约数 gcd 的函数需要背下来。

注意题目的 corner case，如果两个字符串 A + B != B + A 的话，说明两者是没有公共子串的。

复杂度

时间O(log min(a, b))
空间O(1)

代码

Java实现

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // corner case
        if (!str1.concat(str2).equals(str2.concat(str1))) {
            return "";
        }

        // normal case
        int gcdLength = helper(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }

    private int helper(int a, int b) {
        if (a == 0) {
            return b;
        }
        if (b == 0) {
            return a;
        }
        if (a == b) {
            return a;
        }
        if (a > b) {
            return helper(a % b, b);
        }
        return helper(b, a % b);
    }
}

// gcd, 辗转相除法