1071. Greatest Common Divisor of Strings

[songyy5517]

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + 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: ""

Intuition This problem mainly examines the properties of String. The whole task can be broken down into two sections: 1. Determine whether two strings contain common divisor; 2. Find their greatest common divisor. For the first one, we can check whether str1 + str2 == str2 + str1 . To obtain their GCD, we can first calculate the GCD of their length, then the result is the substring(0, GCD).

[songyy5517]

Approach: Repeating String Property & GCD

1. Exception Handling & Repeating String Determination;
   • str1 + str2 == str2 + str1
2. Find GCD of these two strings:
   • Use Euclidean Algorithm to calculate the GCD of their length;
   • The GCD string is the substring(0, GCD) of these two strings.
3. Return the substring.

Complexity Analysis

• Time complexity: $O(M+N)$ , $M, N$ are the length of str1 and str2 respectively, the concatenation of these two strings costs $O(M+N)$ , and the time complexity of Euclidean Algorithm is $O(log_2N)$ . Therefore, the entire complexity is $O(M+N+logN) = O(M+N)$ .
• Space complexity: $O(M+N)$ , temperary space is used to store the concatenation string.

[songyy5517]

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // Intuition: 判断循环串 & 求循环串。
        // 1. Exception Handling

        if (str1 == null || str2 == null || !(str1 + str2).equals(str2 + str1))
            return "";

        // 2. Compute GCD
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }

    // 辗转相除法：求最大公因数GCD: greatest common divisor
    int gcd(int x, int y){
        int rem = x % y;
        while (rem != 0){
            x = y;
            y = rem;
            rem = x % y;
        }

        return y;
    }
}

[songyy5517]

2024/5/6