1071. 字符串的最大公因子

分析

1. 判断条件：

   • 首先，字符串 str1 能否被 str2 整除以及 str2 能否被 str1 整除的关键条件是：str1 + str2 == str2 + str1。如果这个条件不成立，则不存在一个字符串能够同时整除这两个字符串，返回空字符串

2. 最大公因子：

   • 如果 str1 + str2 == str2 + str1，则可以根据字符串的长度来进一步判断最大公因子。
   • 假设 str1 的长度为 n1，str2 的长度为 n2，那么最大公因子字符串的长度应该是 gcd(n1, n2)。我们可以利用 gcd 函数计算出 n1 和 n2 的最大公因子，取 str1 或 str2 的前 gcd(n1, n2) 个字符作为最大公因子字符串

3. 核心步骤：

   • 判断 str1 + str2 == str2 + str1，如果不成立，返回 ""
   • 计算 gcd(len(str1), len(str2))，然后返回 str1 的前 gcd 长度的子串

时间复杂度

• 计算 gcd 的时间复杂度是 O(logmin(n1, n2))，其中 n1 和 n2 是 str1 和 str2 的长度
• 字符串比较的时间复杂度是 O(n1 + n2)
• 截取子串的时间复杂度是 O(gcd(n1, n2))，由于 gcd(n1, n2) 最大为 min(n1, n2)，因此总体时间复杂度是 O(n1 + n2)

空间复杂度

空间复杂度为 O(n1 + n2)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
    // 计算两个数的最大公因子
    int gcd(int a, int b)
    {
        return b ? gcd(b, a % b) : a;
    }

    // 返回能够同时整除 str1 和 str2 的最大公因子字符串
    string gcdOfStrings(string str1, string str2)
    {
        // 如果 str1 + str2 != str2 + str1，则不存在公共因子
        if (str1 + str2 != str2 + str1)
            return "";

        // 否则返回 str1 的前 gcd(str1.size(), str2.size()) 长度的子串
        return str1.substr(0, gcd(str1.size(), str2.size()));
    }
};