1071.Greatest Common Divisor of Strings
===

###### tags: `Easy`,`Math`,`String`

[1071. Greatest Common Divisor of Strings](https://leetcode.com/problems/greatest-common-divisor-of-strings/)

### 題目描述

For two strings `s` and `t`, we say "`t` divides `s`" if and only if `s = t + ... + t` (i.e., `t` is concatenated with itself one 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: ""

**Constraints**:

* 1 <= `str1.length`, `str2.length` <= 1000
* `str1` and `str2` consist of English uppercase letters.

### 解答

#### C++
##### 思路
- 如果gcdString存在，也就是兩個字串都是由gcdString組成，則這兩個字串無論先後，相加起來的結果一定相同。
- 所有的cdString也會是gcdString的一部分，因此直接針對兩個字串長度取最大公因數就好。

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

> [name=Yen-Chi Chen][time=Wed, Feb 1, 2023]

#### Python

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        return str1[:gcd(len(str1), len(str2))] if str1 + str2 == str2 + str1 else ""

> [name=Yen-Chi Chen][time=Wed, Feb 1, 2023]

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        
        n = min(len(str1), len(str2))
        gcd = ''
        while n != 0:
            if len(str1) % n == 0 and len(str2) % n == 0:
                gcd = str1[0:n]
                print(n, len(str1), len(str2))
                #check str1
                flag1 = (str1 == gcd*(len(str1)//n) )
                #check str2
                flag2 = (str2 == gcd*(len(str2)//n) )

                if flag1 and flag2:
                    return str1[:n]
                else:
                    n -= 1
            else:
                n -= 1
        return ""

> [name=玉山]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)