难度: Easy
对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
示例 1：
输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC"
示例 2：
输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB"
示例 3：
输入：str1 = "LEET", str2 = "CODE" 输出：""
提示：
1 <= str1.length, str2.length <= 1000str1 和 str2 由大写英文字母组成运行时间: 20 ms
内存: 0.0 MB
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if not str1 and str2: return str1 or str2
if len(str2) > len(str1): return self.gcdOfStrings(str2, str1)
if str1[: len(str2)] == str2:
return self.gcdOfStrings(str1[len(str2) :], str2)
else: return ''
本题的解法基于最大公因子的概念，适用递归方法求解两个字符串的最大公因子。首先，如果其中一个字符串为空，则另一个字符串就是最大公因子。如果`str1`的长度小于`str2`，为了方便处理，将它们交换。接着检查`str1`是否以`str2`开头，如果是，则去掉`str1`前面的`str2`部分，对剩余的字符串和`str2`继续求最大公因子。如果`str1`不以`str2`开头，说明它们没有公共前缀，最大公因子为空字符串。这个方法利用了字符串的结构特性，通过递归减小问题规模。
时间复杂度: O(n * min(m, n))
空间复杂度: O(min(m, n))
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if not str1 and str2: return str1 or str2 # 如果一个字符串为空，则返回另一个
if len(str2) > len(str1): return self.gcdOfStrings(str2, str1) # 保证str1不比str2短
if str1[: len(str2)] == str2: # 检查str1是否以str2开头
return self.gcdOfStrings(str1[len(str2):], str2) # 如果是，则递归处理剩余部分
else: return '' # 如果不是，返回空字符串
首先检查`str1`是否以`str2`为前缀是为了确认`str2`是否可能是`str1`的一个重复段，即`str2`可能是`str1`的因子。如果`str1`以`str2`开始，这意味着`str1`可以被`str2`部分或完全覆盖。这是解决问题的关键步骤，因为最大公因子必须是两个字符串的共同前缀。如果`str1`以`str2`开头，我们可以去掉这部分，继续递归寻找剩余部分与`str2`的最大公因子，这样逐步缩小问题的规模。如果`str1`不以`str2`开头，那么两者没有公共前缀，最大公因子只能是空字符串。
每次递归去掉`str1`前面的`str2`部分后，剩余的`str1`（如果有）仍然与原始的`str2`保持结构一致性，即它们可能仍存在共同的重复模式。这种方法的有效性基于假设，如果`str1`可以分解为多个`str2`，那么剩余部分（如果不为空）自然也应该能被`str2`分解。因此，通过对剩余部分与`str2`继续递归处理，我们可以逐步找到它们的最大公因子，直至完全无法再分解为止，这样可以确保递归过程中始终在寻找有效的最大公因子。
在递归过程中，如果`str1`变得非常短但是仍然比`str2`长，这时候会再次检查`str1`是否以`str2`为前缀。如果不是，根据算法的逻辑，直接返回空字符串作为最大公因子，递归终止。如果是，`str1`将继续被`str2`的长度分割，直到`str1`的长度小于或等于`str2`的长度。在每一步递归中，我们都有明确的逻辑来处理不同的情况，确保算法能够在有限的步骤后正确终止。如果两者长度最终相等且内容相同，则递归返回`str2`；如果不相同，则返回空字符串。