LeetCode.1071.Greatest Common Divisor of Strings 字符串的最大公因子

题目描述

1071 Greatest Common Divisor of Strings https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/

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 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

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

解题过程

根据提示 辗转相除法 做出来了，

假设 str1 是 m 个 x，str2 是 n 个 x，那么 str1+str2 = (m+n)x 肯定是等于 str2+str1 = (n+m)x 的

时间复杂度 O(n + logn) = O(n)， 空间复杂度 O(n)

private static class SolutionV2020 {
    public String gcdOfStrings(String str1, String str2) {
        if (null == str1 || null == str2 || str1.length() == 0 || str2.length() == 0) {
            return "";
        }
        // str1 是较长的
        if (str2.length() > str1.length()) {
            String temp = str1;
            str1 = str2;
            str2 = temp;
        }
        // 辗转相除法
        while (str1.indexOf(str2) == 0) {
            String mod = str1.substring(str2.length());
            if (mod.length() == 0) {
                return str2;
            }
            // str1 是较长的
            if (mod.length() > str2.length()) {
                str1 = mod;
            } else {
                str1 = str2;
                str2 = mod;
            }
        }
        return "";
    }
}

GitHub代码

algorithms/leetcode/leetcode/_1071_GreatestCommonDivisorOfStrings.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1071_GreatestCommonDivisorOfStrings.java