问题陈述 1071. 字符串的最大公约数

对于两个字符串 s 和 t，当且仅当 s = t t t ... t t （即 t 与自身连接一次或多次）时，我们才说“t 除 s”。

给定两个字符串 str1 和 str2，返回使 x 整除 str1 和 str2 的最大字符串 x。

我的思考过程

尽管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)，因为我们不需要任何额外的空间。