当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.1071.Greatest Common Divisor of Strings 字符串的最大公因子

LeetCode.1071.Greatest Common Divisor of Strings 字符串的最大公因子

题目描述

1071 Greatest Common Divisor of Strings
https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/

For strings S and T, we say “T divides S” if and only if S = T + … + T (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides str2.

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Note:
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] and str2[i] are English uppercase letters.


解题过程

根据提示 辗转相除法 做出来了,

假设 str1 是 m 个 x,str2 是 n 个 x,那么 str1+str2 = (m+n)x 肯定是等于 str2+str1 = (n+m)x 的

时间复杂度 O(n + logn) = O(n), 空间复杂度 O(n)

private static class SolutionV2020 {
    public String gcdOfStrings(String str1, String str2) {
        if (null == str1 || null == str2 || str1.length() == 0 || str2.length() == 0) {
            return "";
        }
        // str1 是较长的
        if (str2.length() > str1.length()) {
            String temp = str1;
            str1 = str2;
            str2 = temp;
        }
        // 辗转相除法
        while (str1.indexOf(str2) == 0) {
            String mod = str1.substring(str2.length());
            if (mod.length() == 0) {
                return str2;
            }
            // str1 是较长的
            if (mod.length() > str2.length()) {
                str1 = mod;
            } else {
                str1 = str2;
                str2 = mod;
            }
        }
        return "";
    }
}

GitHub代码

algorithms/leetcode/leetcode/_1071_GreatestCommonDivisorOfStrings.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1071_GreatestCommonDivisorOfStrings.java


上一篇 LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

下一篇 LeetCode.1013.Partition Array Into Three Parts With Equal Sum 将数组分成和相等的三个部分

阅读
评论
266
阅读预计1分钟
创建日期 2020-03-12
修改日期 2020-03-12
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论