题目地址：https://leetcode.com/problems/greatest-common-divisor-of-strings/
题目描述
Forstrings 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、 1<=str1.length<=1000；
2、 1<=str2.length<=1000；
3、 str1[i]andstr2[i]areEnglishuppercaseletters.；
题目大意
求两个字符串的最长公共重复子串。重复子串是指原字符串可以有其子串重复若干次得到。
解题方法
暴力遍历
最长公共重复子串重复若干次之后能分别得到str1和str2，那么最明显地，该子串的长度一定是str1和str2长度的公因数。看了一下字符串的长度最多只有1000，所以我们完全可以对长度进行遍历，判断每个公因数是不是构成最长公共重复子串。因为要找最长的，所以找到最长之后，直接返回即可。
时间复杂度O(N^2)。外部循环找到公因数，时间复杂度O(N)；内部要创建新的字符串和原先的字符串进行比较，时间复杂度也是O(N)。
Python代码如下：
class Solution(object):
def gcdOfStrings(self, str1, str2):
"""
:type str1: str
:type str2: str
:rtype: str
"""
l1, l2 = len(str1), len(str2)
shorter = min(l1, l2)
res = ""
for i in range(shorter, 0, -1):
if l1 % i or l2 % i:
continue
t1, t2 = l1 // i, l2 // i
gcd = str1[:i]
rebuild1 = gcd * t1
rebuild2 = gcd * t2
if rebuild1 == str1 and rebuild2 == str2:
res = gcd
break
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
C++代码如下：
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
int l1 = str1.size();
int l2 = str2.size();
int shorter = min(l1, l2);
string res;
for (int i = shorter; i >= 1; --i) {
if ((l1 % i == 0) && (l2 % i == 0)) {
int t1 = l1 / i;
int t2 = l2 / i;
string gcd = str1.substr(0, i);
string rebuild1 = genRepeatStr(t1, gcd);
string rebuild2 = genRepeatStr(t2, gcd);
if ((rebuild1 == str1) && (rebuild2 == str2)) {
res = gcd;
break;
}
}
}
return res;
}
string genRepeatStr(int times, string substr) {
string res;
while (times--) {
res += substr;
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发