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 <= 10001 <= str2.length <= 1000str1andstr2consist 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
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
