题解 | #名字串生成I#

考察的知识点：字符串；

解答方法分析：

1. 获取str1和str2的长度，并使用辗转相除法求出最大公约数，作为可能的最长子串的长度。
2. 构造出一个长度为最长子串长度的子串作为候选子串。
3. 分别检查候选子串是否可以通过重复构造生成str1和str2。
4. 两者都成立，则返回候选子串；否则，返回空字符串。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    string gcdOfStrings(string str1, string str2) {
        int len1 = str1.size();
        int len2 = str2.size();
        int len = gcd(len1, len2);
        string candidate = str1.substr(0, len);
        if (check(candidate, str1) && check(candidate, str2)) {
            return candidate;
        }
        return "";
    }
  private:
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    bool check(string candidate, string str) {
        string temp = "";
        int n = str.size() / candidate.size();

        for (int i = 0; i < n; i++) {
            temp += candidate;
        }
        return temp == str;
    }
};