题目描述

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

样例

输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

输入：str1 = "LEET", str2 = "CODE"
输出：""

注意

• 1 <= str1.length <= 1000
• 1 <= str2.length <= 1000
• str1[i] 和 str2[i] 为大写英文字母

算法

(辗转相减法) $O(n + m)$

1. 由于字符串的除法也只能用减法实现，所以我们采用辗转相减法求最大公约串。
2. 每次用较长字符串的前缀和较短字符串比较，如果不相等，则直接返回空串。否则，将较长串的前缀减掉较短串，继续递归求最大公约串。

时间复杂度

• 字符总数一共有 $O(n + m)$ 个，故消除的总时间复杂度也就是 $O(n + m)$。

空间复杂度

• 递归会占用系统栈空间，最坏情况下需要占用 $O(\max (n, m))$ 的空间。

C++ 代码

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str2.length() == 0)
            return str1;

        if (str1.length() < str2.length())
            swap(str1, str2);

        int n = str1.length(), m = str2.length();
        for (int i = 0; i < m; i++)
            if (str1[i] != str2[i])
                return "";

        return gcdOfStrings(str1.substr(m, n - m), str2);
    }
};