LeetCode: 1071 Greatest Common Divisor of Strings

For two strings s1 and s2, we say "s1 divides s2" if and only if s2 is formed by concatenating one or more copies of s1. Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""

问题

对于两个字符串 s1 和 s2，当且仅当 s2 由一个或多个 s1 连接而成时，我们说 "s1 可以整除 s2"。给定两个字符串 str1 和 str2，返回可以整除 str1 和 str2 的最大字符串 x。

解决方案 1

使用数学上的最大公约数（GCD）概念来解决字符串问题。

Approach 1 / 方法 1

如果 str1 和 str2 有一个非空的公共前缀，它就是它们重复字符串的最大公约数。我们可以通过检查两个字符串是否可以通过该公共前缀整除来验证这一点。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Check if the concatenation of str1 + str2 equals str2 + str1. If not, there is no common divisor.
   检查 str1 + str2 是否等于 str2 + str1。如果不等，则没有公共除数。

Step 1 / 第一步:

2. Compute the GCD of the lengths of str1 and str2.
   计算 str1 和 str2 长度的最大公约数。

Step 2 / 第二步:

3. Return the substring of str1 from index 0 to the GCD of the lengths.
   返回 str1 从索引 0 到长度最大公约数的子字符串。

Implementation / 实现

python

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        gcd_length = gcd(len(str1), len(str2))
        return str1[:gcd_length]

Explanation / 解释

1. Step 1 / 第一步:

• Check if str1 concatenated with str2 equals str2 concatenated with str1. If not, return an empty string.
  检查 str1 和 str2 的连接是否等于 str2 和 str1 的连接。如果不等，返回空字符串。

2. Step 2 / 第二步:

• Compute the GCD of the lengths of str1 and str2.
  计算 str1 和 str2 长度的最大公约数。

3. Step 3 / 第三步:

• Return the substring of str1 from index 0 to the GCD of the lengths.
  返回 str1 从索引 0 到长度最大公约数的子字符串。

Complexity Analysis / 复杂度分析

• Time Complexity: O(N + M), where N and M are the lengths of str1 and str2.
  时间复杂度: O(N + M)，其中 N 和 M 是 str1 和 str2 的长度。

• Space Complexity: O(1)
  空间复杂度: O(1)

Key Concept / 关键概念

• The key concept is to use the properties of string concatenation and the greatest common divisor to find the common divisor string.
  关键概念是利用字符串连接和最大公约数的性质找到公共除数字符串。

解决方案 2

使用递归方法查找字符串的最大公约数。

Approach 2 / 方法 2

通过递归的方法，不断缩短字符串，找到公共前缀。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Define a recursive function to find the GCD of strings.
   定义一个递归函数来查找字符串的最大公约数。

Step 1 / 第一步:

2. In each recursive call, if one string is a prefix of the other, return the common prefix.
   在每次递归调用中，如果一个字符串是另一个字符串的前缀，则返回公共前缀。

Step 2 / 第二步:

3. Recur with the remaining parts of the strings.
   用剩余部分的字符串进行递归。

Implementation / 实现

python

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if not str2:
            return str1
        if str1.startswith(str2):
            return self.gcdOfStrings(str1[len(str2):], str2)
        else:
            return self.gcdOfStrings(str2, str1)

Explanation / 解释

1. Step 1 / 第一步:

• Base case: if str2 is empty, return str1.
  基本情况：如果 str2 为空，则返回 str1。

2. Step 2 / 第二步:

• If str1 starts with str2, recur with the remaining part of str1 and str2.
  如果 str1 以 str2 开头，则对 str1 和 str2 的剩余部分进行递归。

3. Step 3 / 第三步:

• Otherwise, swap the strings and recur.
  否则，交换字符串并递归。

Complexity Analysis / 复杂度分析

• Time Complexity: O(N + M)
  时间复杂度: O(N + M)

• Space Complexity: O(N + M)
  空间复杂度: O(N + M)

Key Concept / 关键概念

• The key concept is to use recursion to find the greatest common divisor of the strings.
  关键概念是使用递归查找字符串的最大公约数。

Tips / 提示

• Ensure to handle edge cases where one string is much longer than the other.
  确保处理一个字符串比另一个字符串长得多的情况。

Solution Template for similar questions / 提示

• The approach can be applied to other problems involving finding common prefixes or divisors of strings.
  该方法可以应用于其他涉及查找字符串公共前缀或除数的问题。

Recommended 5 more similar questions / 推荐5问题

1. LeetCode 14: Longest Common Prefix
2. LeetCode 28: Implement strStr()
3. LeetCode 796: Rotate String
4. LeetCode 459: Repeated Substring Pattern
5. LeetCode 686: Repeated String Match

More

• LeetCode Explore – String
• GeeksforGeeks – String Data Structure
• InterviewBit – String Interview Questions
• Leetcode 75

Recommend Resource

Greatest Common Divisor of Strings – Leetcode 1071 – Python by NeetCodeIO