1071. Greatest Common Divisor of Strings
1. Description
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.
2. Example
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: ""
Example 4
Input: str1 = “AAAAAB”, str2 = “AAA”
Output: ""
3. Constraints
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of English uppercase letters.
4. Solutions
Brute Force
m = str1.size(), n = str2.size()
Time complexity: O(min(m, n)*(m + n))
Space complexity: O(min(m, n))
class Solution {
public:
string gcdOfStrings(const string &str1, const string &str2) {
const string &short_str = str1.size() <= str2.size() ? str1 : str2;
const string &long_str = str1.size() <= str2.size() ? str2 : str1;
string result;
for (int i = short_str.size(); i >= 1; --i) {
if (long_str.size() % i == 0 && short_str.size() % i == 0) {
string pattern = short_str.substr(0, i);
if (is_repeat_pattern(long_str, pattern) && is_repeat_pattern(short_str, pattern)) {
return pattern;
}
}
}
return result;
}
private:
bool is_repeat_pattern(const string &str, const string &pattern) {
for (int i = 0; i < pattern.size(); ++i) {
for (int j = i; j < str.size(); j += pattern.size()) {
if (str[j] != pattern[i]) {
return false;
}
}
}
return true;
}
};
Math
m = str1.size(), n = str2.size()
Time complexity: O(m + n)
Space complexity: O(m + n)
class Solution {
public:
string gcdOfStrings(const string &str1, const string &str2) {
if (str1 + str2 != str2 + str1) {
return string("");
}
int gcd_length = gcd(str1.size(), str2.size());
string result = str1.substr(0, gcd_length);
return result;
}
};