Last Updated on 2023-02-02 by Clay
題目
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 <= 1000str1andstr2consist of English uppercase letters.
題目給定兩個字串輸入，我們要找到一個『最小的字串組成』，且該最小的字串組成可以組合成題目輸入的兩個字串。
什麼意思呢？簡單來說，就像是範例給的 ABABAB 和 ABAB。這兩個字串都可以分別由另一個更小的元件 AB 來組成！而不能單獨由 A 或 B 來組成。這時候，我們就把 AB 視為兩個字串的最小組成，也即是我們要找到的答案。
解題思路
最大公因數（GCD）
我想通的第一件事情，就是 str1 和 str2 若是存在共同的最小組成，那麼 str1+str2 跟 str2+str1 應該會一模一樣！我們就拿範例來舉例：
ABABAB和ABAB無論以何種順序組合，最終結果都一致ABCABC和ABC無論以何種順序組合，最終結果都一致Leet和Code只要以不同順序組合，就會是兩個不同的字串，所以並不存在共同的最小組成！
所以一開始可以優先判斷這件事。
接著，就是在較短的字串中尋找重複出現的最小組成了（若無重複出現的組成，代表該字串本身就是最小組成）。一開始我寫了個暴力法來找，後來參考他人的答案，發現：只要找到 str1 和 str2 長度的『最大公因數』，就代表那是最小組成的長度！
比方說 ABABAB 和 ABAB 的長度分別是 6 和 4，兩者的最小公因數是 2，所以頭 2 個字元（也就是 AB）就是共同的最小組成。
而 ABCABC 和 ABC 的長度則為 6 和 3，最小公因數是 3，所以頭 3 個字元也就是 ABC 就是共同的最小組成。
這是因為我們在第一個條件判斷時，就已經確認了兩個字串存在著一個共同的組成字串，而我們要找的這個最小的共同組成，其實概念上就與兩個數值間的最大公因數相同，只不過我們現在處理的組成是『字串』就是了。
C++ 範例程式碼
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1+str2 != str2+str1) {
return "";
}
return str1.substr(0, gcd(str1.size(), str2.size()));
}
};Python 範例程式碼
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 != str2 + str1:
return ""
return str1[:gcd(len(str1), len(str2))]