题解 | #名字串生成I# gcd

知识点

gcd 字符串

思路

假如答案存在的话，一定是s1和s2的公因数长度的子串。而这些子串全都是最大公因数长度子串的子串，如果某一公因数长度的子串是一个解的话，那么最大公因数长度的子串一定也是一个解，而且最大公因数的子串更长。

所以如果存在的话就是最大公因数长度的子串。

实现上我们可以先求出最大公因数长度的子串，然后去验证是否合法。

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return string字符串
     */
    string gcdOfStrings(string str1, string str2) {
        int n = str1.size(), m = str2.size();
        int k = __gcd(n, m);
        if (str1.substr(0, k) == str2.substr(0, k) and check(str1, k) and check(str2, k)) return str1.substr(0, k);
        return "";
    }
    bool check(const string& s, int len) {
        for (int i = len; i < s.size(); i ++) {
            if (s[i] != s[i % len]) return false;
        }
        return true;
    }
};