题目大意：
字符串的最大公因子
对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1：
输入：str1 = “ABCABC”, str2 = “ABC”
输出：”ABC”
示例 2：
输入：str1 = “ABABAB”, str2 = “ABAB”
输出：”AB”
示例 3：
输入：str1 = “LEET”, str2 = “CODE”
输出：””
提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1071
解题思路分析：
虽然这是一道简单题目，但个人感觉难度偏中等一些。这里给出两种解题思路。
解法一：暴力解。时间复杂度n的平方，执行时间1ms。
既然是求字符串的公因数，所以如果存在答案，这个公因数的长度一定是两个字符串长度的公因数。我们可以从大到小循环所有公因数，以每个公因数的长度n截取字符串的前n位，看看两个字符串是否完全由这n位组成。
看下代码：
public String gcdOfStrings(String str1, String str2) {
if(str1.equals(str2)){ // 如果两字符串相同，返回其中一个字符串即可。
return str2;
}
// 取得2字符串长度
int length1 = str1.length(), length2=str2.length();
// 最大公约数的最大范围（不可能大于较大数的一半以上）
int maxLength = Math.max(length1,length2) / 2;
for(int i=maxLength;i>0;i--){ // 循环查找公约数
if(length1 % i != 0 || length2 % i != 0){
// 如果不能被两字符长度整除，则不是公约数，跳过。
continue;
}
// 以当前公约数为长度截取字符串前i位，取得公约字符串
String common = str1.substring(0, i);
// 查看2字符串是否都由公约字符串组成，是的话，直接返回该公约字符串，否则继续循环
if(isCommon(str1, common) && isCommon(str2, common)){
return common;
}
}
return "";
}
// 检查一个字符串str是否由字符串common组成
boolean isCommon(String str, String common){
for(int i=0;i<str.length();i++){
if(str.charAt(i) != common.charAt(i % common.length())){
return false;
}
}
return true;
}本解法执行时间位1ms。
Runtime: 1 ms, faster than 58.92% of Java online submissions forGreatest Common Divisor of Strings.
Memory Usage: 35.8 MB, less than 100.00% of Java online submissions for Greatest Common Divisor of Strings.
解法2，递归。执行时间0ms。
public String gcdOfStrings(String str1, String str2) {
// 保证str1长度大于str2长度
if (str1.length() < str2.length()){
return gcdOfStrings(str2, str1);
}
// 如果2字符串相同，直接返回其中一个
if (str1.equals(str2)){
return str1;
}
// 如果较短的字符串为空，返回空
if (str2.equals("")){
return str2;
}
// 如果较长字符串1以字符串2开头
if (str1.startsWith(str2)){
// 将字符串1截取掉字符串2的部分，递归道下一步。
// 本题实际递归的终止条件为str1等于str2
return gcdOfStrings(str2, str1.substring(str2.length()));
}
return "";
}本解法执行时间0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions forGreatest Common Divisor of Strings.
Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Greatest Common Divisor of Strings.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1071-greatest-common-divisor-of-strings-解题思路分析/