1071. Greatest Common Divisor of Strings

For two strings s and t, we say “t divides s“ if and only if s = t + ... + t  (t concatenated with itself 1 or more times)

Given two strings str1 and str2, return the largest string x such that x divides both str1 and 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: ""

Example 4:

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

Constraints:

  • 1 <= str1.length <= 1000
  • 1 <= str2.length <= 1000
  • str1 and str2 consist of English uppercase letters.

这道题定义了一种两个字符串s和t之间的整除关系,若s串可由若干个t串组成,则说t串可以整除s串。现在给了两个字符串 str1 和 str2,现在让找到一个最大的字符串x,使得其可以同时整除这两个字符串。来分析一下,由于这个x会重复出现在字符串中,所以其一定是个前缀,则字符串的所有前缀都有可能是这个x,于是乎只要遍历所有的前缀,然后来验证其是否可以整除这两个字符串就可以找到要求的x了。遍历 str1 的所有前缀,若 str1 的长度不是这个前缀的长度的整数倍,或者 str2 的长度不是这个前缀长度的整数倍,直接跳过。否则直接分别复制前缀直到和 str1,str2 的长度相同,再比较,若完全一样,则说明前缀是一个x,赋值给结果 res。这样遍历下来就能得到长度最长的x了,参见代码如下:

解法一:

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        string res;
        int m = str1.size(), n = str2.size();
        for (int i = 0; i < m; ++i) {
            if (m % (i + 1) != 0 || n % (i + 1) != 0) continue;
            string pre = str1.substr(0, i + 1), target1, target2;
            for (int j = 0; j < m / (i + 1); ++j) {
                target1 += pre;
            }
            if (target1 != str1) continue;
            for (int j = 0; j < n / (i + 1); ++j) {
                target2 += pre;
            }
            if (target2 != str2) continue;
            res = pre;
        }
        return res;
    }
};

这道题用递归来做的话会变的异常的简洁,我们仔细来观察题目中给的例子,若存在这样的x的话,那么短的字符串一定是长的字符串的子串,比如例子1和例子2。这样的话其实是可以化简的,当长串中的前缀(和短串的长度相同)不等于短串的时候,说明x不存在,可以直接返回空,否则从长串中取出和短串长度相同的前缀,继续调用递归,直到其中一个为空的时候,返回另一个就可以了,参见代码如下:

解法二:

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1.size() < str2.size()) return gcdOfStrings(str2, str1);
        if (str2.empty()) return str1;
        if (str1.substr(0, str2.size()) != str2) return "";
        return gcdOfStrings(str1.substr(str2.size()), str2);
    }
};

下面这种解法一行搞定碉堡了,由于 str1 和 str2 可以被同一个x串整除,那么 str1+str2 和 str2+str1 一定是相同的,不信大家可以自行带例子去验证。而且最大的x的长度是 str1 和 str2 长度的最大公约数相同(是不是感觉很神奇,求大佬证明),这样的话直接浓缩到一行就搞定了,参见代码如下:

解法三:

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        return (str1 + str2 == str2 + str1) ? str1.substr(0, gcd(str1.size(), str2.size())) : "";
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1071

参考资料:

https://leetcode.com/problems/greatest-common-divisor-of-strings/

https://leetcode.com/problems/greatest-common-divisor-of-strings/discuss/307242/C%2B%2B-3-lines

https://leetcode.com/problems/greatest-common-divisor-of-strings/discuss/303759/My-4-Lines-C%2B%2B-Solution

https://leetcode.com/problems/greatest-common-divisor-of-strings/discuss/303781/JavaPython-3-3-codes-each%3A-Recursive-iterative-and-regex-w-brief-comments-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)


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

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation