1071、字符串的最大公因子

leetcode

Created At : 2020-07-26 00:19

Count:702 Views 👀 :

Comment:

1071、字符串的最大公因子
题解

1071、字符串的最大公因子

对于字符串 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-cn.com/problems/greatest-common-divisor-of-strings

题解

1、模拟整除运算

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        String res = "";
        // 第一个字母不匹配，肯定不能除尽
        if (str1.charAt(0) != str2.charAt(0)) {
            return res;
        }
        // str1存长串
        if (str1.length() < str2.length()) {
            String t = str1;
            str1 = str2;
            str2 = t;
        }
        // 构建结果
        StringBuilder sb = new StringBuilder();
        for (char ch : str2.toCharArray()) {
            sb.append(ch);
            String x = sb.toString();
            // 同时x可以被str1,str2整除
            if (canDivisible(str1,x) && canDivisible(str2,x)) {
                // 更新结果
                res = sb.toString();
            }
        }
        return res;
    }
    // 字符串整除判断函数，判断str1是否能被x整除
    private boolean canDivisible(String str1,String x) {
        if (str1.length() % x.length() != 0) {
            return false;
        }
        for (int i = 0;i < str1.length()/x.length();i++) {
            int start = i*x.length();
            String substr = str1.substring(start,start + x.length());
            if (!substr.equals(x)) {
                return false;
            }
        }
        return true;
    }
}

2、整除子串的等价形式

若存在x可以同时整除str1和str2，那么str1+srt2 = str2+str1,且x.length为str1.length 和 str2.length的最大公约数。

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        String res = "";
        // 第一个字母不匹配，肯定不能除尽
        if (str1.charAt(0) != str2.charAt(0)) {
            return res;
        }
        StringBuilder sb1 = new StringBuilder();
        sb1.append(str1).append(str2);
        StringBuilder sb2 = new StringBuilder();
        sb2.append(str2).append(str1);
        if (sb1.toString().equals(sb2.toString())) {
            res = str1.substring(0,gcd(str1.length(),str2.length()));
        }
        return res;
    }
    private int gcd(int a,int b) {
        if(b!=0) while((a%=b)!=0 && (b%=a)!=0);
        return a+b;
    }
}

3、递归实现字符串的辗转相除法

class Solution {
    // 只有在 S = T + ... + T，才认定 “T 能除尽 S”
    // 返回一个字符串 X，要求即能除尽 str1 又能除尽 str2（其实就是最大公约数）
    // 也就是说 str1 = X + ... + X，且 str2 = X + ... + X
    // 使用辗转相除法
    // gcb(a, b) => a == 0 ? b : gcb(b, a % b);
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        if (len1 == 0) {
            return str2;
        }
        // 长的字符串在前面
        if (len2 > len1) {
            return gcdOfStrings(str2, str1);
        }
        // String类的判断是否为前缀的函数
        if (!str1.startsWith(str2)) {
            return "";
        }
        // 这里辗转相处和 a % b 有些区别，a % b 可能会去除 n 个 b 只留下余数
        // 但是对于 str，只能每一去掉一个 b！
        return gcdOfStrings(str2, str1.substring(len2, len1));
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com