1071. Greatest Common Divisor of Strings

[jason89521]

Practice Dates

• 2024/05/10

Description

Link: https://leetcode.com/problems/greatest-common-divisor-of-strings/description/

Solution

Find the largest divisor of the shorter string, then check whether the divisor can also divide the longer string. If it can, return it. Otherwise, find the next largest divisor.

If all divisor of the shorter string cannot divide the longer string, return an empty string.

bool is_divisor(string divisor, string target) {
    string str = divisor;
    while (str.length() < target.length()) {
        str = str + divisor;
    }

    return str == target;
}

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        string min = str1.length() < str2.length() ? str1 : str2;
        string max = min == str1 ? str2 : str1;
        for (int i = min.length(); i > 0; i--) {
            if (min.length() % i != 0 || max.length() % i != 0) {
                continue;
            }
            string substr = min.substr(0, i);
            if (is_divisor(substr, min) && is_divisor(substr, max)) {
                return substr;
            }
        }

        return "";
    }
};

Performance

Time complexity: O(min⁡(m,n)⋅(m+n))

[jason89521]

Better Approach

There is a better approach, with a time complexity of O(m + n). I should figure it out by myself next time I try to solve this problem.