Leetcode：字串的最大公約數

問題陳述 1071. 字串的最大公約數

對於兩個字串s 和t，當且僅當s = t + t + t + ... + t + t （即t 與自身連接一次或多次）時，我們才說「t 除s」。

給定兩個字串 str1 和 str2，傳回最大的字串 x，使得 x 整除 str1 和 str2。

我的思考過程

儘管leetcode將其標記為簡單問題，但我必須承認我發現很難立即想出解決方案。

讓我回顧一下 leetcode 提供的測試案例並透過它們來解釋我的困惑。

測試用例

輸入：str1 = "ABCABC", str2 = "ABC"
輸出：“ABC”

輸入：str1 = "ABABAB", str2 = "ABAB"
輸出：“AB”

從問題陳述和測試案例 1 中，我確實確定我們需要輸出最大的字串（“ABC”），連接起來我們可以得到兩個字串。 （預設字串“ABC”=== str2 和“ABC”+“ABC”=== str1）。

但是，查看測試案例 2，我很快意識到我的理解不正確，因為我應該輸出“ABAB”，因為這是我可以創建兩個字串的最長字串。但我開始編寫程式碼並開始製定解決方案。 （菜鳥錯誤？）

失敗/成功的事

我只能訂定一個解決方案：

1. 求兩個字串的 GCD。
2. 從最小字串的長度迭代到GCD
3. 從最小字串中取一個子字串到目前迭代值。
4. 如果兩個字串都包含該子字串，則傳回該子字串作為答案。
5. 如果沒有找到字串，則傳回「」。

如您所見，對於 str1 包含 str2 但還包含一些其他附加字元的字串，我的解決方案失敗了。違反了 s = t + t + ... + t + t 的要求。

我必須向neetcode的解決方案尋求協助。我很快就明白我的問題了：

1. 我正在尋找字串長度的 GCD，而不是字串本身。我需要找到一個字串，重複這些字串我可以創建兩個字串而沒有任何剩餘字元。

2. 我意識到為什麼「ABAB」不能作為測試案例 2 的答案：

• 我們需要找到 x 以便將兩個字串均分。因此，以“ABAB”作為字串，您可以完全創建 str2，但對於 str1，您最終會得到“ABABABAB”。你最終會得到 2 個多餘的“AB”，並且不能說你完全透過組合 x 創建了 str1。

• 「ABAB」長度為 4 和「ABABAB」長度為 6。2 個字串的 GCD = 2。因此輸出需要是長度為 2 的字串。

輸出

時間與空間複雜度

時間複雜度：

在最壞的情況下，我們迭代Min(str1,str2) 並且需要重新建立str1 和str2，這樣總時間將是(str1.length + str2.length)複雜度將為O(min(str1,str2) * (str1.length + str2.length))

空間複雜度：

O(1)，因為我們不需要任何額外的空間。

以上是Leetcode：字串的最大公約數的詳細內容。更多資訊請關注PHP中文網其他相關文章！