Easy

题目描述

对于字符串 s 和 t，我们说 “t 整除 s” 当且仅当 s = t + t + … + t（即 t 与自身连接 1 次或多次）。

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：str1 = "AAAAAB", str2 = "AAA"
输出：""

约束条件：

  • 1 <= str1.length, str2.length <= 1000
  • str1 和 str2 由英文大写字母组成

解题思路

这道题的关键在于理解字符串的最大公因数概念。如果一个字符串 x 能同时整除两个字符串，那么这两个字符串都必须是 x 的整数倍重复。

主要思路：

  1. 数学关系验证：如果存在字符串最大公因数，那么 str1 + str2 应该等于 str2 + str1。这是因为如果两个字符串都由同一个模式重复组成，那么拼接顺序不会影响结果。

  2. 长度关系：字符串的最大公因数长度必须是两个字符串长度的最大公约数。这是因为如果 x 的长度为 len，那么 str1 的长度必须是 len 的倍数，str2 的长度也必须是 len 的倍数。

  3. 算法步骤：

    • 首先检查 str1 + str2 是否等于 str2 + str1
    • 如果不等，说明不存在公共的重复模式，返回空字符串
    • 如果相等，计算两个字符串长度的最大公约数 gcd_len
    • 返回 str1 的前 gcd_len 个字符

这种方法利用了数学中最大公约数的性质，避免了复杂的字符串匹配过程，是最优解法。

代码实现

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        // 检查是否存在公共模式
        if (str1 + str2 != str2 + str1) {
            return "";
        }
        
        // 计算两个字符串长度的最大公约数
        int gcd_len = gcd(str1.length(), str2.length());
        
        // 返回最大公因数字符串
        return str1.substr(0, gcd_len);
    }
    
private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        import math
        
        # 检查是否存在公共模式
        if str1 + str2 != str2 + str1:
            return ""
        
        # 计算两个字符串长度的最大公约数
        gcd_len = math.gcd(len(str1), len(str2))
        
        # 返回最大公因数字符串
        return str1[:gcd_len]

public class Solution {
    public string GcdOfStrings(string str1, string str2) {
        // 检查是否存在公共模式
        if (str1 + str2 != str2 + str1) {
            return "";
        }
        
        // 计算两个字符串长度的最大公约数
        int gcdLen = Gcd(str1.Length, str2.Length);
        
        // 返回最大公因数字符串
        return str1.Substring(0, gcdLen);
    }
    
    private int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
}

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function(str1, str2) {
    if (str1 + str2 !== str2 + str1) return "";
    
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    
    return str1.substring(0, gcd(str1.length, str2.length));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m + n)，其中 m 和 n 分别是两个字符串的长度。主要耗时在字符串拼接和比较上
空间复杂度O(m + n)，用于存储拼接后的字符串进行比较

相关题目