Leetcode 1071: Greatest Common Divisor of Strings

Brute Force:

Algorithm

Find the shorter string among str1 and str2, without loss of generality, let it be str1.
Start with base = str1, and check if both str1 and str2 are made of multiples of base.
- If so, return base.
- Otherwise, we shall try a shorter string by removing the last character from base.
If we have checked all prefix strings without finding the GCD string, return "".

				
					class Solution {
    public boolean valid(String str1, String str2, int k) {
        int len1 = str1.length(), len2 = str2.length();
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            String base = str1.substring(0, k);
            return str1.replace(base, "").isEmpty() && str2.replace(base, "").isEmpty();
        }
    }
    
    
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; --i) {
            if (valid(str1, str2, i)) {
                return str1.substring(0, i);
            }
        }
        return "";
    }
}

Approach 2: Greatest common divisor

Algorithm

Check if the concatenations of str1 and str2 in different orders are the same.
- If not, return "".
Get the GCD gcdLength of the two lengths of str1 and str2.
Return the prefix string with a length of gcdLength of either str1 or str2 as the answer.

				
					class Solution {
    public int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }    
    }
    
    public String gcdOfStrings(String str1, String str2) {
        // Check if they have non-zero GCD string.
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        
        // Get the GCD of the two lengths.
        int gcdLength = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }
}

Complexity Analysis

Let $m, n$ be the lengthes of the two input strings str1 and str2.

Time complexity: $O (m + n)$
- We need to compare the two concatenations of length $O (m + n)$ , it takes $O (m + n)$ time.
- We calculate the GCD using binary Euclidean algorithm, it takes $log (m \cdot n)$ time.
- To sum up, the overall time complexity is $O (m + n)$ .
Space complexity: $O (m + n)$
We need to compare the two concatenations of length $O (m + n)$ .

DareToDream

Leetcode 1071: Greatest Common Divisor of Strings

Brute Force:

Algorithm

Approach 2: Greatest common divisor

Algorithm

Complexity Analysis

Leave a Comment Cancel Reply