Greatest Common Divisor of Strings
題目描述
給定兩個字串 str1 和 str2，找出能同時整除兩個字串的最長字串。字串 t 能整除字串 s 表示 s 可以由 t 重複拼接而成。
輸入：str1 = "ABCABC", str2 = "ABC"
輸出："ABC"
輸入：str1 = "ABABAB", str2 = "ABAB"
輸出："AB"
輸入：str1 = "LEET", str2 = "CODE"
輸出：""
解題思路
檢查可行性
拼接 str1+str2 與 str2+str1 比較，若不相等代表不存在任何公因子字串，直接回傳空字串
求 GCD 長度
用歐幾里得演算法對 len(str1) 和 len(str2) 求最大公因數，例如 GCD(6,3)=3
截取候選
取 str1 的前 gcd_len 個字元作為答案，因為拼接檢查已保證該子字串能重複組成兩字串
程式碼
C#
public class Solution {
public string GcdOfStrings(string str1, string str2) {
// 若拼接順序不同結果不同，代表沒有公因子
if (str1 + str2 != str2 + str1) return "";
// 用 GCD 求出最大公因子長度
int gcdLen = Gcd(str1.Length, str2.Length);
return str1.Substring(0, gcdLen);
}
private int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b);
}TypeScript
function gcdOfStrings(str1: string, str2: string): string {
// 拼接檢查
if (str1 + str2 !== str2 + str1) return "";
const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
return str1.substring(0, gcd(str1.length, str2.length));
}Python
from math import gcd
def gcdOfStrings(str1: str, str2: str) -> str:
# 拼接檢查：如果沒有公因子，拼接順序會不同
if str1 + str2 != str2 + str1:
return ""
return str1[:gcd(len(str1), len(str2))]複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n + m) | O(n + m) |
拼接比較需要逐字元比對 O(n+m)，GCD 計算為 O(log(min(n,m)))，瓶頸在拼接比較。空間上，拼接產生兩個長度為 n+m 的新字串。
邊界情況
- 兩字串完全相同：例如
"ABC"和"ABC"，GCD 長度等於字串本身長度，答案就是字串自身 - 其中一個是另一個的倍數：例如
"ABCABC"和"ABC"，GCD(6,3)=3，答案為"ABC" - 完全無公因子：例如
"LEET"和"CODE"，拼接檢查不通過，直接回傳空字串
圖解
圖表展示兩階段判斷：先確認 ABCABC+ABC 是否等於 ABC+ABCABC（兩者都是 ABCABCABC，通過）。再用數學 GCD 算出公因子長度為 3，直接截取前 3 字元 ABC 即為答案。
進階觀點
💡面試追問
-
Q: 為什麼
str1+str2 == str2+str1就保證有公因子？ A: 這是充要條件。若存在公因子 t，兩字串可表示為 t 的重複拼接（str1 = t^a, str2 = t^b），拼接後 t^(a+b) = t^(b+a) 自然相等。反過來，若拼接相等，可以數學歸納證明 str1 的前 GCD(n,m) 個字元必定能重複組成兩字串。 -
Q: 暴力法怎麼做？ A: 從較短字串的長度開始，由大到小檢查每個能同時整除 n 和 m 的候選長度 L。取 str1 的前 L 個字元為候選 t，驗證 t 重複 n/L 次是否等於 str1、重複 m/L 次是否等於 str2。找到第一個就回傳。最壞要檢查所有公因數，每次驗證 O(n+m)。
-
Q: 時間複雜度的瓶頸在哪？ A: 在字串拼接比較 O(n+m)，需要逐字元比對兩個長度為 n+m 的字串。GCD 計算用歐幾里得演算法只需 O(log(min(n,m)))，substring 截取 O(GCD(n,m))，都被拼接比較的 O(n+m) 主導。
理解測驗
🤔 str1 = "LEET", str2 = "CODE"，為什麼答案是空字串？
🤔 GCD 在這題中扮演什麼角色？