5076-字符串的最大公因子
文章目录
前言
Weekly Contest 139的 字符串的最大公因子:
对于字符串
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 <= 10001 <= str2.length <= 1000str1[i]和str2[i]为大写英文字母
解题思路
本题需要注意,如果字符串S和T本身不是有特定字符串循环组成的,那么其实字符串S和T直接也不存在一个最大公因子。我的解题思路是将问题进行分解,分解为以下3步:
- 提取循环因子:判断字符串是否由特定字符循环组成,并找出所有可以组成字符串的循环字符串
- 提取公因子:字符串
S和T的循环因子结果进行并集计算 - 提取最大公因子:从公因子集合中找出长度最大的字符串
实现代码
/**
* 5076. 字符串的最大公因子
* @param str1
* @param str2
* @return
*/
public String gcdOfStrings(String str1, String str2) {
List<String> loopStr1=findLoopStrings(str1);
List<String> loopStr2=findLoopStrings(str2);
List<String> union=new ArrayList<>();
if(!loopStr1.isEmpty() && !loopStr2.isEmpty()){// 不存在循环因子
for(String l1:loopStr1){// 进行并集运算,提取公因子
for (String l2: loopStr2) {
if(l1.equals(l2)){
union.add(l1);
}
}
}
if(union.isEmpty()){// 无公因子,直接返回空字符
return "";
}
// 找出长度最大的字符串
return union.stream().collect(Collectors.maxBy(Comparator.comparing(String::length))).get();
}
return "";
}
/**
* 获取组成循环字符串的子串
* @param str
* @return
*/
private List<String> findLoopStrings(String str){
List<String> result=new ArrayList<>();
for(int i=0;i<str.length();i++){
// 循环子串
String subStr=str.substring(0,i+1);
if(str.length()%subStr.length()==0){// 子串长度可以被原字符串长度整除
// 比较次数
int times= str.length()/subStr.length();
// 是否匹配
boolean match=true;
for(int j=0;j<times;j++){
if(!str.substring(j*subStr.length(),(j+1)*subStr.length()).equals(subStr)){
match=false;
break;
}
}
if(match){
result.add(subStr);
}
}
}
return result;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论