1071. Greatest Common Divisor of Strings

Easy

Description

給定兩個字串 str1 和 str2，找出最大的字串 x，使得 x 能整除 str1 和 str2（即 str1 和 str2 都可以由 x 重複拼接而成）。

Example:

Input: str1 = “ABCABC”, str2 = “ABC” Output: “ABC”

Intuition#

核心思路：如果 GCD 字串存在，則 str1 + str2 == str2 + str1，且 GCD 字串的長度等於兩字串長度的 GCD。

若兩字串有公因子字串，則交換拼接結果必須相同
GCD 字串的長度必定是兩字串長度的最大公因數
先驗證 str1 + str2 == str2 + str1，再用長度 GCD 截取結果

Approaches#

1: 暴力列舉#

概念: 列舉所有可能的 GCD 字串長度（從大到小），找到第一個能整除兩字串的
時間複雜度: O(min(m,n) * (m+n)) - 每個候選長度需要驗證
空間複雜度: 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 + 拼接驗證#

概念: 若 str1 + str2 != str2 + str1 則無解；否則答案就是前 gcd(len1, len2) 個字元
時間複雜度: O(m + n) - 字串拼接比較
空間複雜度: 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 問題
關鍵技巧: str1 + str2 == str2 + str1 是判斷公因子字串存在的充要條件，非常優雅