题目考察的知识点

字符串处理，最小公倍数

题目解答方法的文字分析

题目要求找出一个最短的子串，这个子串既可以由牛A的名字str1生成，也可以由牛B的名字str2生成。这就意味着这个子串必须是str1和str2的公倍串。

思路：

  1. 首先，如果str1和str2的长度不相等，那么它们不可能有公倍串，直接返回空串。
  2. 其次，如果str1和str2相等，那么它们的公倍串就是str1（或str2，因为两个相等）本身，直接返回str1即可。
  3. 现在考虑str1和str2长度不相等的情况，首先求出str1和str2的长度的最小公倍数（LCM）lcm，如果str1和str2的长度没有公倍数，那么它们不可能有公倍串，直接返回空串。否则，我们将str1和str2拼接在一起形成一个新的字符串lcmStr，长度为lcm。
  4. 遍历lcmStr，检查它是否满足条件，即是否能够重复构成str1和str2。
  5. 如果遍历过程中发现有不满足条件的字符，则返回空串。
  6. 否则，lcmStr就是str1和str2的公倍串，且为最短公倍串。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <string>
using namespace std;

class Solution {
public:
    string lcmOfStrings(string str1, string str2) {
        int len1 = str1.size();
        int len2 = str2.size();
        int lcm = LCM(len1, len2); // 求str1和str2长度的最小公倍数

        string lcmStr = str1 + str2; // 将str1和str2拼接在一起形成一个新的字符串

        // 遍历lcmStr，检查它是否满足条件，即是否能够重复构成str1和str2
        for (int i = 0; i < lcm; ++i) {
            if (lcmStr[i % len1] != lcmStr[i % len2]) {
                return "";
            }
        }

        return lcmStr.substr(0, lcm); // 返回最短公倍串
    }

private:
    // 辗转相除法求最大公约数
    int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }

    // 最小公倍数 = 两数之积 / 最大公约数
    int LCM(int a, int b) {
        return a * b / GCD(a, b);
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！