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

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

查看所有标签

猜你喜欢:

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

奔跑吧,程序员

奔跑吧,程序员

[美]叶夫根尼·布里克曼(Yevgeniy Brikman) / 吴晓嘉 / 人民邮电出版社 / 2018-7 / 99.00元

本书以软件工程师出身的创业者的角度,全面介绍了创业公司该如何打造产品、实现技术和建立团队,既是为创业者打造的一份实用入门指南,又适合所有程序员系统认识IT行业。书中内容分为三部分——技术、产品和团队,详细描绘创业的原始景象,具体内容包括:创业点子、产品设计、数据与营销、技术栈的选择、整洁的代码、软件交付、创业文化、招兵买马,等等。一起来看看 《奔跑吧,程序员》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

html转js在线工具
html转js在线工具

html转js在线工具