# 1071. Greatest Common Divisor of Strings

For two strings `s` and `t`, we say “`t` divides `s`“ if and only if `s = t + ... + t`  (`t` concatenated with itself 1 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: ""
``````

Example 4:

``````Input: str1 = "ABCDEF", str2 = "ABC"
Output: ""
``````

Constraints:

• `1 <= str1.length <= 1000`
• `1 <= str2.length <= 1000`
• `str1` and `str2` consist of English uppercase letters.

``````class Solution {
public:
string gcdOfStrings(string str1, string str2) {
string res;
int m = str1.size(), n = str2.size();
for (int i = 0; i < m; ++i) {
if (m % (i + 1) != 0 || n % (i + 1) != 0) continue;
string pre = str1.substr(0, i + 1), target1, target2;
for (int j = 0; j < m / (i + 1); ++j) {
target1 += pre;
}
if (target1 != str1) continue;
for (int j = 0; j < n / (i + 1); ++j) {
target2 += pre;
}
if (target2 != str2) continue;
res = pre;
}
return res;
}
};
``````

``````class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1.size() < str2.size()) return gcdOfStrings(str2, str1);
if (str2.empty()) return str1;
if (str1.substr(0, str2.size()) != str2) return "";
return gcdOfStrings(str1.substr(str2.size()), str2);
}
};
``````

``````class Solution {
public:
string gcdOfStrings(string str1, string str2) {
return (str1 + str2 == str2 + str1) ? str1.substr(0, gcd(str1.size(), str2.size())) : "";
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1071

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

https://leetcode.com/problems/greatest-common-divisor-of-strings/discuss/307242/C%2B%2B-3-lines

https://leetcode.com/problems/greatest-common-divisor-of-strings/discuss/303759/My-4-Lines-C%2B%2B-Solution