1071. Greatest Common Divisor of Strings
For two strings s and t, we say “t divides s” if and only if s = 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
bool helper(string str1, string str2) {
if(str1.size() % str2.size()) return false;
int cnt = str1.size() / str2.size();
string tmp = "";
for(int i = 0; i < cnt; i++) tmp += str2;
return tmp == str1;
}
public:
string gcdOfStrings(string str1, string str2) {
for(int i = str2.length(); i >= 1; i--) {
if(str2.length() % i) continue;
if(str1.length() % i) continue;
string cut = str2.substr(0,i);
if(helper(str1,cut) and helper(str2,cut)) return cut;
}
return "";
}
};
|
