要求找到兩個字符串的最大公約數。最大公約數是指能夠同時整除兩個數字的最大正整數。

str2中的字串可以組成str1

思考
1.在string中兩個string是否能成為"有效"的公約字串 和在數字中找到最大公約數不同
條件為 (str1 + str2) == (str2 + str1)。這一步是確保 str1 和 str2 可以形成循環字符串

if(str1 + str2 == str2 + str1)

成立代表兩個string有相同的prefix(前綴) 才有可能成為有效的公約字串
Ex:
str1 = ABCABC, str2 = ABC
ABCABCABC == ABCABCABC 成立
gcd(6,3) = 3 最大可能公約數為三個

Ex:
str1 = CODE str2 = LIFE
CODELIFE != LIFECODE

Ex:
str1 = ABABABAB str2 = ABABA
ABABAABABABAB != ABABABABABABA

2.從str1中拆解出最大可能前綴(0, 公因數), 從str1中擷取回傳
這裡使用了 C++ 的 __gcd 函數（內建函數）來計算 str1 和 str2 的長度的最大公因子，然後再使用 substr 函數取出 str1 的前 gcd 個字符作為結果。

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        //先判斷兩個字串有沒有可能成為最大公因數
        if(str1 + str2 == str2 + str1){
            //擷取最大可能的prefix
            return str1.substr(0, __gcd(str1.size(), str2.size()));
        }
        return "";
    }
};

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        // 字串的最大公約數代表這個字串可以組成str1和str2
        // s = t + t + t.... + t 也就是確保 循環字串
        // 代表 s + t 和 t + s是要相等
        if(str1 + str2 != str2 + str1){
            return "";
        }else{
            //代表str1和str2是有公因字串的，最大公因字串的size可以整除兩個字串的size
            return str1.substr(0, __gcd(str1.size(), str2.size()));
        }
    }
};

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function(str1, str2) {
    // str1 可以被 str2 構造
    // 要能持為循環才有機會
    if(str1 + str2 != str2 + str1){
        return "";
    }else{
        const n = gcd(str1.length, str2.length);
        console.log(n);
        return str1.substring(0, n)
    }



    function gcd(a, b){
        if(b === 0){
            return a;
        }
        return gcd(b, a % b);
    }
};