給定兩個字串
str1和str2，找出最大的字串x，使得x能整除str1和str2（即str1和str2都可以由x重複拼接而成）。
Example:
Input: str1 = “ABCABC”, str2 = “ABC” Output: “ABC”
Intuition
TIP
核心思路：如果 GCD 字串存在，則 str1 + str2 == str2 + str1，且 GCD 字串的長度等於兩字串長度的 GCD。
- 若兩字串有公因子字串，則交換拼接結果必須相同
- GCD 字串的長度必定是兩字串長度的最大公因數
- 先驗證
str1 + str2 == str2 + str1，再用長度 GCD 截取結果
Approaches
1. Brute-Force Enumeration — O(min(m,n) * (m+n)) / O(min(m,n))
- Idea: 列舉所有可能的 GCD 字串長度（從大到小），找到第一個能整除兩字串的
- Time:
O(min(m,n) * (m+n))- 每個候選長度需要驗證 - Space:
O(min(m,n))- 候選字串
class Solution {
fun gcdOfStrings(str1: String, str2: String): String {
val minLen = minOf(str1.length, str2.length)
for (len in minLen downTo 1) {
if (str1.length % len == 0 && str2.length % len == 0) {
val candidate = str1.substring(0, len)
if (candidate.repeat(str1.length / len) == str1 &&
candidate.repeat(str2.length / len) == str2) {
return candidate
}
}
}
return ""
}
}⭐ 2. GCD + Concatenation Check — O(m + n) / O(m + n)
- Idea: 若
str1 + str2 != str2 + str1則無解；否則答案就是前gcd(len1, len2)個字元 - Time:
O(m + n)- 字串拼接比較 - Space:
O(m + n)- 拼接後的字串
class Solution {
fun gcdOfStrings(str1: String, str2: String): String {
if (str1 + str2 != str2 + str1) return ""
val gcdLen = gcd(str1.length, str2.length)
return str1.substring(0, gcdLen)
}
private fun gcd(a: Int, b: Int): Int {
return if (b == 0) a else gcd(b, a % b)
}
}🔑 Takeaways
- Pattern: 將字串問題轉化為數學 GCD 問題
- Key trick:
str1 + str2 == str2 + str1是判斷公因子字串存在的充要條件，非常優雅