Loading [MathJax]/jax/output/HTML-CSS/jax.js

由字符串A重复x次和字符串B重复y次连接形成的最短字符串，满足n(A)*x = n(B)*y

在这个问题中，我们需要找到最短的字符串，它是字符串A和字符串B的倍数。这个问题非常类似于寻找两个数字的最小公倍数(LCM)。我们可以找到两个字符串长度的最小公倍数，通过自身连接使两个字符串的长度等于最小公倍数。之后，我们可以比较字符串，检查是否可以得到最短的字符串，它是A和B的倍数。

问题陈述 – 我们给定不同长度的字符串A和字符串B。我们需要找到最短的字符串，它是字符串A和字符串B的倍数。

注意 – 如果可以通过将第一个字符串自身连接多次来获得第二个字符串，则第一个字符串是第二个字符串的倍数。

示例

输入

A = "ddd", B = "d";

输出

‘ddd’

解释 – 字符串“ddd”是A的倍数，也是B的倍数，因为1*A = 3*B。

输入

A = "abc", B = "def";

输出

-1

解释 – 因为两个字符串不同，所以无法找到最短的字符串，它是A和B的倍数。

输入

A = "abcabcabc", B = "abcabc";

输出

‘abcabcabcabcabcabc’

解释 – 输出显示，最短的字符串是A和B的倍数，因为2*A == 3*B。

方法一

这种方法将找到两个字符串长度的最大公约数(GCD)。之后，我们将使用GCD找到最小公倍数(LCM)。根据LCM值，我们将把两个字符串自身连接多次，并匹配最终字符串以检查它们是否相等。

算法

步骤1 – 定义getGCD()函数来查找两个数字的最大公约数，它以第一个和第二个作为参数。

步骤1.1 – 如果第一个等于零，则返回第二个。

步骤1.2 – 获取第二个对第一个的模，并将其作为GCD函数的第一个参数，同时进行递归调用。

步骤2 – 在multipleOfAandB()函数中，用字符串A和字符串B的长度初始化len1和len2变量。

步骤3 – 执行getGCD()函数以获得两个数字的最大公约数，并将其存储在gcd变量中。

步骤4 – 接下来，将len1和len2相乘，然后除以GCD值以获得LCM值。

步骤5 – 初始化两个名为temp1和temp2的临时字符串，用于存储相乘后的字符串。

步骤6 – 将字符串A追加到temp1，重复LCM/len1次。

步骤7 – 将字符串B追加到temp2，重复LCM/len2次。

步骤8 – 如果temp1和temp2相等，则打印temp1或temp2的值。否则，打印-1。

示例

Open Compiler
#include <bits/stdc++.h>
using namespace std;

// Get GCD of numbers
int getGCD(int first, int second){
    if (first == 0) {
        return second;
    }
    return getGCD(second % first, first);
}
void multipleOfAandB(string A, string B){
    int len1 = A.length();
    int len2 = B.length();
    int gcd = getGCD(len1, len2);
    // Get LCM of len1 and len2
    int lcm = (len1 * len2) / gcd;
    // To store multiple of A
    string temp1 = "";
    // To store multiple of B
    string temp2 = "";
    // string concatenation
    for (int m = 0; m < (lcm / len1); m++) {
        temp1 = temp1 + A;
    }
    // string concatenation
    for (int m = 0; m < (lcm / len2); m++) {
        temp2 = temp2 + B;
    }
    // Compare temp1 and temp2
    if (temp1 == temp2) {
        cout << "The resultnat string is - " << temp1;
    } else {
        cout << -1;
    }
}
int main() {
    string A = "ddd";
    string B = "d";
    multipleOfAandB(A, B);
    return 0;
}

输出

The resultnat string is - ddd

时间复杂度 – O(log(N*M))，因为我们找到了长度的GCD并连接了字符串

空间复杂度 – O(N + M)，因为我们需要存储最短字符串。

这个问题的解决方案与寻找两个数字的最小公倍数非常相似，但是我们需要确保在这里，字符串在多次连接后应该是相同的。

更新于：2023年8月25日

85 次查看

开启你的职业生涯

完成课程获得认证

开始学习
广告