LeetCode 日記 #003：1071. 重新複習 GCD 為何物？了解字串最大公因數的特性

For two strings s and t, we say "t divides s" if and only if s = t + t + t + … + t + t (i.e., t is concatenated with itself one or more times).Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

這道題目的描述有幾個重點：

1. t divides s: 在數學或計算機領域，t divides s 意思是 t 可以整除 s 的意思，代表字串 t 可以重複構成字串 s 且不會有任何剩餘的字元。
2. If and only if: 這是在數學、邏輯學、計算機科學領域常用到的邏輯短語，通常縮寫為 iff。簡單來說就是一個「互為因果」的雙向關係，比如說假設 A 是我爸，那我一定是 A 的兒子。

也就是說題目會給兩個字串，要找出可以整除這兩個字串的最長字串，即「最大公因數」。

解題策略

而解法簡單分為三步驟：

1. 排除邊界案例：檢查兩個字串是否存在最大公因數。判斷前需要先了解字串裡最大公因數的特性：

   若兩個有公因數的話，str1 + str2 = str2 + str1。
   不符合這個條件則返回空字串。

2.找出兩個字串長度的最大公因數，用歐基里德算法。

3.找出後取出任意字串匹配的最大公因長度。

完整題解

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if(!(str1 + str2).equals(str2 + str1)) {
            return "";
        }

        int gcdLength = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }

    // 計算兩個數的最大公約數
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

/**
- 思考最大公因數的本質：
對於字符串的最大公因數問題，有一個重要性質：
如果str1 + str2 == str2 + str1，則存在最大公因數；否則不存在。
- 最大公因數的長度就是 str1 和 str2 長度的最大公約數（數學上的GCD）。
 */

Complexity

引用 Claude AI。Cause I have no idea about analyze the time and space complexity of this problem. Still learning…

時間複雜度: O(m + n)

1. 字串拼接和比較：
   str1 + str2 和 str2 + str1 的操作涉及創建新的字符串，其時間複雜度為 O(m + n)，其中 m 和 n 是兩個字符串的長度。比較兩個字符串是否相等需要 O(m + n) 時間。

2. 計算最大公約數：
   使用歐幾里得算法計算 gcd 的時間複雜度為 O(log(min(m, n)))，其中 m 和 n 是兩個數的大小。

3. 提取子字符串：
   substring 操作的時間複雜度為 O(gcdLength)，最壞情況下是 O(min(m, n))。

空間複雜度: O(m + n)

1. 字符串拼接：
   str1 + str2 和 str2 + str1 創建了兩個新的字符串，每個長度為 m + n，因此空間複雜度為 O(m + n)。

2. 遞迴調用：
   歐幾里得算法的遞迴深度為 O(log(min(m, n)))，但通常這個遞迴深度很小，可以忽略不計。

3. 結果字符串：
   最終返回的子字符串長度最多為 min(m, n)，空間複雜度為 O(min(m, n))。

結論

時間複雜度：O(m + n)，這可以簡化為 O(n)，如果我們用 n 表示兩個字符串的總長度。
空間複雜度：O(m + n)，主要來自於字符串拼接操作。

注意：如果不考慮字串拼接創建的臨時字符串（比如在某些語言或實現中可能有優化），那麼空間複雜度可能會降低，但在一般的 Java 實現中，它是 O(m + n) 而不是 O(1)。