LeetCode 1071. 字符串的最大公因子

Categories:

题目描述
思路分析
1. 解法一：拼接验证 + GCD（推荐）
相似题目

题目描述

✅ 1071. 字符串的最大公因子

思路分析

解法一：拼接验证 + GCD（推荐）

核心思路：

若 str1 + str2 != str2 + str1，则不存在公共重复子串。

否则答案长度为 gcd(len1, len2)，返回对应前缀。

利用最大公因数确定重复周期。

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串总长度。

空间复杂度：O(1)（忽略拼接临时）。

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        int g = gcd(str1.length(), str2.length());
        return str1.substring(0, g);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

func gcdOfStrings(str1 string, str2 string) string {
    if str1+str2 != str2+str1 {
        return ""
    }
    g := gcd(len(str1), len(str2))
    return str1[:g]
}

func gcd(a int, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

相似题目

题目	难度	考察点
28. 找出字符串中第一个匹配项的下标	简单	字符串
459. 重复的子字符串	简单	字符串
686. 重复叠加字符串匹配	中等	字符串
1071. 字符串的最大公因子	简单	GCD
1392. 最长快乐前缀	困难	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/42198328