Leetcode：字符串的最大公约数

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

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

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

我的思考过程

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

以上是Leetcode：字符串的最大公约数的详细内容。更多信息请关注PHP中文网其他相关文章！