blob: 420eb102cd96e6dd5642896374d12cffe5bc54eb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
// 1071. Greatest Common Divisor of Strings
#include "leetcode.h"
/*
* for two strings 's' & 't', we say 't' divides 's' if and only if s = t + ...
* + t ie. 't' is concatenated with itself one or more times given two strings
* 'str1' & 'str2', return largest string 'x' such that 'x' divides both 'str1'
* & 'str2'
*/
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
/* first check if finding gcd is even possible
* eg. ABAB + AB == AB + ABAB
* LEET + CODE != CODE + LEET
*/
if (str1 + str2 == str2 + str1) {
// get gcd of string sizes
// eg. ABAB (4) and AB (2), gcd = 2
int gcd = __gcd(str1.size(), str2.size());
// return substring of (either) string
// beginning at element 0 and a length of gcd
return str1.substr(0, gcd);
// if gcd isn't possible, return empty string
} else
return "";
}
};
int main() {
Solution obj;
cout << obj.gcdOfStrings("ABCABC", "ABC") << endl; // expect: ABC
cout << obj.gcdOfStrings("ABABAB", "ABAB") << endl; // expect: AB
cout << obj.gcdOfStrings("LEET", "CODE") << endl; // expect: n/a
}
|