Greatest Common Divisor Of Strings

1071. 字符串的最大公因子

分析

判断条件：
- 首先，字符串 str1 能否被 str2 整除以及 str2 能否被 str1 整除的关键条件是：str1 + str2 == str2 + str1
- 如果这个条件不成立，则不存在一个字符串能够同时整除这两个字符串，返回空字符串
最大公因子：
- 如果 str1 + str2 == str2 + str1，则可以根据字符串的长度来进一步判断最大公因子
- 假设 str1 的长度为 n1，str2 的长度为 n2，那么最大公因子字符串的长度应该是 gcd(n1, n2)
- 利用 gcd 函数计算出 n1 和 n2 的最大公因子，取 str1 或 str2 的前 gcd(n1, n2) 个字符作为最大公因子字符串

时间复杂度

字符串比较的时间复杂度是 O(n1 + n2)
gcd(n1, n2) 时间复杂度：O(log 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()));
    }
};