[LeetCode] 1071. Greatest Common Divisor of Strings

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)