前言说明
算法学习，日常刷题记录。
题目连接
题目内容
对于字符串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]为大写英文字母
分析过程
第一步
如果是字符串的最大公因子，肯定是两个字符串str1和str2中短字符串的某个前缀，而且前缀的长度必须同时是两个字符串str1和str2的长度的约数。
第二步
获取字符串str1的长度为length1，获取字符串str2的长度为length2，算出字符串str1和字符串str2的较小长度，然后开始从较小长度遍历到1，从大到小遍历。
第三步
遍历时，判断前缀的长度是否同时是两个字符串str1和str2的长度的约数。
如果不满足，直接跳到下一次遍历。
第四步
如果满足，通过substring的方法获取前缀，定义为str。这里获取前缀str时，用其中的一个字符串切割即可获取到，因为在获取较小长度时，已经限定了前缀str在较小长度的字符串里。
然后调用函数judgeCommon两次，第一次输入前缀str和字符串str1，第二次输入前缀str和字符串str2，如果两次调用都返回true结果，那么字符串str1和字符串str2拥有公因子，公因子就是前缀str。
而前缀str的长度是从大到小遍历的，所以这里一旦找到符合条件的前缀str，前缀str就是最大公因子，即可把前缀str作为返回结果。
第五步
遍历结束后，若不能找到符合条件的前缀str，那么把空字符串作为返回结果。
函数judgeCommon
此函数定义了输入前缀t和字符串s，判断前缀t是否为字符串s的因子。
在函数judgeCommon中，因为字符串s等于多个字符串t相加，即S = T + ... + T(T自身连接1次或多次)，所以用字符串s的长度除以字符串t的长度，获取倍数length，即length = s.length() / t.length()。
定义字符串集合sb，遍历倍数length次，每次字符串集合sb添加字符串t。
遍历结束后，若字符串集合sb刚好就等于字符串s，那么表示前缀t能除尽字符串s，即前缀t是字符串s的因子。
解答代码
class Solution {
public String gcdOfStrings(String str1, String str2) {
// 思路：答案肯定是某个字符串的前缀，如果要满足最大公因子的条件，前缀的长度必须同时是两个字符串str1和str2的长度的约数
// 获取字符串str1的长度
int length1 = str1.length();
// 获取字符串str2的长度
int length2 = str2.length();
// 求出字符串str1和字符串str2的较小长度，从较小长度遍历到1，从大到小遍历
for (int i = Math.min(length1, length2); i >= 1; --i) {
// 判断前缀的长度是否同时是两个字符串str1和str2的长度的约数
if (length1 % i == 0 && length2 % i == 0) {
// 获取前缀，用其中的一个字符串切割即可，因为最大范围已经限定在了较小长度里
String str = str1.substring(0, i);
if (judgeCommon(str, str1) && judgeCommon(str, str2)) {
// 若前缀和字符串str1、前缀和字符串str2都满足因子关系，那么字符串str1和字符串str2拥有公因子str，因为前缀的长度是从大到小遍历的，所以这里一旦找到符合条件的前缀，即可以返回结果str
return str;
}
}
}
// 若不能找到符合条件的前缀，返回空字符串
return "";
}
// 定义判断是否满足字符串因子的函数
private boolean judgeCommon(String t, String s) {
// 因为字符串s等于多个字符串t相加，所以用字符串s的长度除以字符串t的长度，获取倍数length
int length = s.length() / t.length();
// 定义字符串集合sb
StringBuilder sb = new StringBuilder();
// 遍历倍数length次，每次字符串集合sb添加字符串t
for (int i = 0; i < length; ++i) {
sb.append(t);
}
// 最后若字符串集合sb刚好就等于字符串s，那么满足字符串t能除尽字符串s，即满足字符串t是字符串s的字符串因子的条件
return s.equals(sb.toString());
}
}
提交结果
执行用时1ms，时间击败94.93%的用户，内存消耗38.2MB，空间击败90.13%的用户。
运行结果
原文链接
原文链接：字符串的最大公因子
网友评论