首页　>　文章列表　>　Typescript 编码编年史：字符串的最大公约数

Typescript 编码编年史：字符串的最大公约数

255 2024-07-16

问题陈述：

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

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

示例1：

输入：str1 = "abcabc", str2 = "abc"
输出：“abc”

示例2：

输入：str1 =“ababab”，str2 =“abab”
输出：“ab”

示例3：

输入：str1 =“leet”，str2 =“code”
输出：“”

限制条件：

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

了解问题：

为了解决这个问题，我们需要找到重复时可以同时形成 str1 和 str2 的最大字符串。这个问题类似于寻找两个数字的最大公约数 (gcd)，但我们处理的是字符串。

初步思考过程：

我们需要确定这两个字符串是否具有可以重复形成这两个字符串的共同模式。如果 str1 + str2 等于 str2 + str1，则存在公约数字符串。这个公共字符串的长度将是 str1 和 str2 长度的 gcd。

基本解决方案：

基本方法包括连接字符串并检查条件 str1 + str2 === str2 + str1。如果这是真的，那么解决方案将是 str1 的子字符串，直到其长度的 gcd 长度。

代码：

function gcdofstringsbasic(str1: string, str2: string): string {
    // helper function to find the greatest common divisor of two numbers
    function gcd(a: number, b: number): number {
        if (b === 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // check if str1 + str2 is the same as str2 + str1
    if (str1 + str2 !== str2 + str1) {
        return "";
    }

    // find the greatest common divisor of the lengths of str1 and str2
    let gcdlength = gcd(str1.length, str2.length);

    // return the substring of str1 or str2 from 0 to gcdlength
    return str1.substring(0, gcdlength);
}

时间复杂度分析：

时间复杂度： o(n + m)，其中n是str1的长度，m是str2的长度。串联检查需要 o(n + m) 时间，gcd 计算需要 o(log(min(n, m)))。
空间复杂度： 连接字符串的 o(n + m) 和 gcd 计算的 o(1)。

限制：

考虑到问题的限制，基本解决方案是有效的。它利用字符串连接和 gcd 计算来实现所需的结果。

优化方案：

基本的解决方案已经相当优化，但我们可以确保代码尽可能高效和干净。我们将重用 gcd 计算函数，并采用更简化的方法来检查公约数。

代码：

function gcdofstringsoptimized(str1: string, str2: string): string {
    // helper function to find the greatest common divisor of two numbers
    function gcd(a: number, b: number): number {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    }

    // check if str1 + str2 is the same as str2 + str1
    if (str1 + str2 !== str2 + str1) {
        return "";
    }

    // find the greatest common divisor of the lengths of str1 and str2
    let gcdlength = gcd(str1.length, str2.length);

    // return the substring of str1 or str2 from 0 to gcdlength
    return str1.substring(0, gcdlength);
}

时间复杂度分析：

时间复杂度： o(n + m)，其中n是str1的长度，m是str2的长度。串联检查需要 o(n + m) 时间，gcd 计算需要 o(log(min(n, m)))。
空间复杂度： gcd 计算为 o(1)，因为串联检查不存储额外的字符串。

基本解决方案的改进：

优化后的解决方案对 gcd 函数使用迭代方法，在某些环境下比递归方法更高效。
它还避免了创建不必要的新字符串，从而稍微提高了空间效率。

边缘情况和测试：

边缘情况：

str1 是 str2 的倍数。
str2 是 str1 的倍数。
str1 和 str2 没有公约数。
str1 或 str2 为空。

测试用例：

console.log(gcdOfStringsBasic("ABCABC", "ABC")); // "ABC"
console.log(gcdOfStringsBasic("ABABAB", "ABAB")); // "AB"
console.log(gcdOfStringsBasic("LEET", "CODE")); // ""
console.log(gcdOfStringsBasic("ABCDEF", "ABC")); // ""
console.log(gcdOfStringsBasic("AAAAAA", "AA")); // "AA"
console.log(gcdOfStringsBasic("AA", "A")); // "A"

console.log(gcdOfStringsOptimized("ABCABC", "ABC")); // "ABC"
console.log(gcdOfStringsOptimized("ABABAB", "ABAB")); // "AB"
console.log(gcdOfStringsOptimized("LEET", "CODE")); // ""
console.log(gcdOfStringsOptimized("ABCDEF", "ABC")); // ""
console.log(gcdOfStringsOptimized("AAAAAA", "AA")); // "AA"
console.log(gcdOfStringsOptimized("AA", "A")); // "A"