3/12题解

1.对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings
方法一：枚举

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int len1=(int)str1.length();
        int len2=(int)str2.length();
        for(int i=min(len1,len2);i>=1;i--)//返回最长，因此从最长的字符串开始枚举
        {
            if(len1%i==0&&len2%i==0)//长度可以被两个字符串都整除
            {
                 string str=str1.substr(0,i);
                 if(check(str,str1)&&check(str,str2))
                     return str;
            }
        }
        return "";

    }
    bool check(string t,string str)
    {
        int sum=(int)str.length()/(int)t.length();//计算有几个子长度
        string check="";
        for(int i=1;i<=sum;i++)
        {
            check+=t;
        }
        return check==str;
    }
};

方法二：如果 str1 和 str2 拼接后等于 str2和 str1 拼接起来的字符串（注意拼接顺序不同），那么一定存在符合条件的字符串 X

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1) return "";
        return str1.substr(0, __gcd((int)str1.length(), (int)str2.length())); // __gcd() 为c++自带的求最大公约数的函数

        return "";
    }
};