1071. Greatest Common Divisor of Strings

📘 題目敘述

對於兩個字串 s 和 t，只有在 s = t + t + t + ... + t（也就是 t 重複串接一次或多次）時，我們才說「t 可以整除 s」。

給定兩個字串 str1 與 str2，請回傳最大的字串 x，使得 x 同時可以整除 str1 與 str2。

條件限制

• 1 ≤ str1.length, str2.length ≤ 1000
• str1 與 str2 只包含英文大寫字母

🧠 解題思路（一）但TLE

我的想法是先從「長度」下手：

• 如果某個字串 x 能整除 str1 和 str2
• 那 x 的長度一定同時是 str1.length 與 str2.length 的公因數
• 所以我先算出兩個長度的最大公因數 mgcd
• 再把 mgcd 的所有因數列出來（從大到小試）
• 每次拿一個長度 L，取 str1 的前 L 個字元當候選字串 rep
• 檢查 str1、str2 是否都能被 rep 以「一段一段相同」的方式完整組成
• 只要成功，第一個成功的 rep 就是答案（因為我由大到小試）

所有變數（對應程式碼）

• m：str1 的長度
• n：str2 的長度
• mgcd：gcd(m, n)，兩個長度的最大公因數
• factor：用來存 mgcd 的所有因數（我用由大到小的順序存，方便直接從最大候選開始試）
• rep：目前嘗試的候選字串（取 str1 的前 L 個字元）
• check：這個 rep 是否同時能整除 str1 與 str2
• check1：在 str1 中，目前比對到的位置（每次成功就往後跳 L）
• check2：在 str2 中，目前比對到的位置（每次成功就往後跳 L）

🪜 主要流程步驟（一）

步驟一：先求長度的最大公因數 mgcd

• 因為答案 x 的長度一定是兩個字串長度的公因數
• 所以我先算 mgcd = gcd(m, n)

步驟二：列出 mgcd 的所有因數（由大到小）

• 我把所有 mgcd 的因數放進 factor
• 這樣可以保證我先試最大的長度，找到就直接回傳（就是「最大」公因字串）

步驟三：對每個候選長度 L 做驗證

對於每個 L = factor[j]：

1. 取候選字串 rep = str1.substr(0, L)
2. 檢查 str1 是否能被 rep 完整拼出來
   • 我用 check1 從 0 開始，每次比對一段長度 L
   • 只要某段有任何字元不一樣，check = false
3. 若 str1 成功，再用同樣方法檢查 str2
   • 用 check2 一段一段比對
4. 若兩邊都完全通過，代表 rep 同時整除兩個字串
   • 直接 return rep

步驟四：都找不到就回傳空字串

• 若所有因數長度都試完仍失敗
• 代表不存在共同的整除字串
• 回傳 ""

💻 程式碼實作

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int m = str1.size();
        int n = str2.size();
        int mgcd = gcd(m, n);
        vector<int> factor;
        for (int i = mgcd; i > 0; i--) {
            if (mgcd % i == 0) {
                factor.push_back(i);
            }
        }

        for (int j = 0; j < factor.size(); j++) {
            int check1 = 0, check2 = 0;
            bool check = true;
            string rep = str1.substr(0, factor[j]);
            while (check1 < str1.size() && check) {
                for (int k = 0; k < factor[j]; k++) {
                    if (str1[check1 + k] != rep[k]) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    check1 += factor[j];
                }
            }

            while (check2 < str2.size() && check) {
                for (int l = 0; l < factor[j]; l++) {
                    if (str2[check2 + l] != rep[l]) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    check2 += factor[j];
                }
            }

            if (check) {
                return rep;
            }
        }
        return "";
    }
};

🧠 解題思路（二）更簡單想法

我後來發現這題其實可以用一個很關鍵的判斷，把整個流程大幅簡化：

• 如果 str1 和 str2 真的都是由同一個字串 x 重複組成
• 那它們的「拼接順序」應該不影響結果
• 也就是必須滿足：str1 + str2 == str2 + str1
• 只要這個條件成立，答案的長度就一定是 gcd(m, n)
• 最後回傳 str1 的前 gcd(m, n) 個字元即可

所有變數

• m：str1 的長度
• n：str2 的長度
• rep：gcd(m, n)，也就是答案字串的長度

🪜 主要流程步驟（二）

步驟一：先檢查是否可能有共同的「重複基底」

if (str1 + str2 != str2 + str1) {
    return "";
}

• 如果兩個字串不是由同一個模式重複出來
• 那拼接後的結果會不一樣
• 這時候代表不可能有共同的 x，直接回傳 ""

步驟二：用長度的最大公因數決定答案長度

int rep = gcd(m, n);

• 當 str1、str2 都是同一個字串重複組成時
• 能同時整除兩者的最大字串長度，一定是 gcd(m, n)

步驟三：取出答案

return str1.substr(0, rep);

• 直接取 str1 的前 rep 個字元
• 這段就是最大的共同整除字串

💻 程式碼實作

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int m = str1.size();
        int n = str2.size();
        if (str1 + str2 != str2 + str1) {
            return "";
        }
        int rep = gcd(m, n);
        return str1.substr(0, rep);
    }
};

🔗 題目連結

https://leetcode.com/problems/greatest-common-divisor-of-strings/