LeetCode刷题-字符串的最大公因子

前言说明

算法学习，日常刷题记录。

题目连接

字符串的最大公因子

题目内容

对于字符串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%的用户。

运行结果

原文链接

原文链接：字符串的最大公因子