题目描述
对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
Example1:
输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC"
Example2:
输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB"
Example3:
输入：str1 = "LEET", str2 = "CODE" 输出：""
提示
- 1 <= str1.length <= 1000
- 1 <= str2.length <= 1000
- str1[i] 和 str2[i] 为大写英文字母
解题思路
- 暴力
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
int len1 = str1.size();
int len2 = str2.size();
for(int i = min(len1, len2); i >= 1; i--){ // 暴力，从最长的开始，看是否能够被整除
if(len1 % i == 0 && len2 % i == 0){
string X = str1.substr(0, i);
if(check(X, str1) && check(X, str2)){
return X;
}
}
}
return "";
}
bool check(string t, string s){
int lenx = s.size() / t.size();
string ans = "";
for(int i = 1; i <= lenx; i++){
ans += t;
}
return ans == s;
}
};
