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

@TOC

## # 题目描述

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. 1 <= str1.length <= 1000
2. 1 <= str2.length <= 1000
3. str1[i] and str2[i] are English uppercase letters.

## # 解题方法

### # 暴力遍历

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
``````

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;
}
};
``````

## # 日期

2019 年 6 月 8 日 —— 刷题尽量不要停