題目

對(duì)于字符串 S 和 T，只有在 S = T + ... + T（T 與自身連接 1 次或多次）時(shí)，我們才認(rèn)定 “T 能除盡 S”。

返回最長(zhǎng)字符串 X，要求滿足 X 能除盡 str1 且 X 能除盡 str2。

示例 1：

輸入：str1 = "ABCABC", str2 = "ABC"
輸出："ABC"
示例 2：

輸入：str1 = "ABABAB", str2 = "ABAB"
輸出："AB"
示例 3：

輸入：str1 = "LEET", str2 = "CODE"
輸出：""

提示：

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 為大寫英文字母

解析

• 首先，先判斷兩個(gè)字符串互相連接是否相等，不等的話直接返回空
• 然后，求兩個(gè)字符串長(zhǎng)度的最大公約長(zhǎng)度
  *然后截取最大長(zhǎng)度的子字符串

代碼

   //其實(shí)是最大公約數(shù)的變種
    public string GcdOfStrings(string str1, string str2)
    {
        if (str1 + str2 != str2 + str1) return "";
        return str1.Substring(0, MaxDivi(str1.Length, str2.Length));
    }

    int MaxDivi(int len1,int len2)
    {
        return len2 == 0 ? len1 : MaxDivi(len2, len1 % len2);
    }