5076-字符串的最大公因子

栏目: ASP.NET · 发布时间: 5年前

内容简介:本题需要注意,如果字符串

前言

Weekly Contest 139字符串的最大公因子

对于字符串 ST ,只有在 S = T + ... + TT 与自身连接 1 次或多次)时,我们才认定 “ T 能除尽 S ”。

返回字符串 X ,要求满足 X 能除尽 str1X 能除尽 str2

示例1:

输入:str1 = "ABCABC", str2 = "ABC"
输出:"ABC"

示例2:

输入:str1 = "ABABAB", str2 = "ABAB"
输出:"AB"

示例3:

输入:str1 = "LEET", str2 = "CODE"
输出:""

提示:

  1. 1 <= str1.length <= 1000
  2. 1 <= str2.length <= 1000
  3. str1[i]str2[i] 为大写英文字母

解题思路

本题需要注意,如果字符串 ST 本身不是有特定字符串循环组成的,那么其实字符串 ST 直接也不存在一个最大公因子。我的解题思路是将问题进行分解,分解为以下 3 步:

  1. 提取循环因子:判断字符串是否由特定字符循环组成,并找出所有可以组成字符串的循环字符串
  2. 提取公因子:字符串 ST 的循环因子结果进行并集计算
  3. 提取最大公因子:从公因子集合中找出长度最大的字符串

实现代码

/**
     * 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;
    }

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

架构整洁之道

架构整洁之道

【美】Robert C. Martin(罗伯特 C. 马丁) / 电子工业出版社 / 2018-9 / 99.00元

《架构整洁之道》是创造“Clean神话”的Bob大叔在架构领域的登峰之作,围绕“架构整洁”这一重要导向,系统地剖析其缘起、内涵及应用场景,涵盖软件研发完整过程及所有核心架构模式。《架构整洁之道》分为6部分,第1部分纲领性地提出软件架构设计的终极目标,描述软件架构设计的重点与模式;第2~4部分从软件开发中三个基础编程范式的定义和特征出发,进一步描述函数、组件、服务设计与实现的定律,以及它们是如何有效......一起来看看 《架构整洁之道》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试