博客

LeetCode——字符串的最大公因子

题目如下：

对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

Example 1:

Input: str1 = “ABCABC”, str2 = “ABC”

Output: “ABC”

Example 2:

Input: str1 = “ABABAB”, str2 = “ABAB”

Output: “AB”

Example 3:

Input: str1 = “LEET”, str2 = “CODE”

Output: “”

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我给出的解答：

string gcdOfStrings(string str1, string str2) {
	string s1 = str1; string s2 = str2;//防止swap后，swap之后的新str1和形参str1傻傻分不清
	int size1 = s1.length(); int size2 = s2.length();  int cFactor = 1;//commonFactor最大公因子
	if (size1 > size2) swap(s1, s2);//整明白那个长那个短，标注出来
	size1 = s1.length();  size2 = s2.length();
	vector<int> factor;
	for (size_t i = 1; i <=size1; i++)
	{
		if (size1 % i == 0 && size2 % i == 0) {
			factor.push_back(i);
			cFactor = i;
		}
	}//找出最大公因数cFactor和每个公因数
	int n = factor.size();//公因数个数
	for (size_t k = 1; k <= n; k++)
	{
		int fac= factor[n - k];
		string t;//在此公因数作为长度截取较短的那一个
		for (size_t i = 0; i < fac; i++) t.push_back( s1[i]);
		int i = 0; int count=0;
		while (i<size2)
		{
			if (s2[i] == t[(i + fac) % fac]) ++i;
			else 
			{ 
				count = -4; //随便赋个好区分的值
				break;
			}
		}
		if (count !=-4 ) count = 1;
		i = fac;
		if (i == size1 && count!=-4) return t; //正好是短的那个字符串
		else
		{
			while (i < size1)
			{
				if (s1[i] == t[i % fac]) i++;
				else {
				count = -4; 
				break;
				}
			}
		}
		if (count != -4 ) count++;
		if (count == 2) return t;
	}
	return "";
}

效率很是不错。

官方解答：

    bool check(string t,string s){//检查string片段t是否能组成字符串s
        int lenx = (int)s.length() / (int)t.length();
        string ans = "";
        for (int i = 1; i <= lenx; ++i){
            ans = ans + t;
        }
        return ans == s;
    }
    string gcdOfStrings(string str1, string str2) {//gcd Greatest Common Divisor 最大公约数，不是暗喻
        int len1 = (int)str1.length(), len2 = (int)str2.length();
        for (int i = min(len1, len2); i >= 1; --i){ // 从长度的最大可能开始枚举
            if (len1 % i == 0 && len2 % i == 0){//如果不是因子直接pass
                string X = str1.substr(0, i);
                if (check(X, str1) && check(X, str2)) return X;
            }
        }
        return "";
    }
//可取之处：直接判断公因子，并且把string当成整体来看，碎片拼接而成

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/zi-fu-chuan-de-zui-da-gong-yin-zi-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1. 其中用到的min()函数选择大小。
2. substr（）函数返回字符串的其中一部分，其中substr的用法为substr（string，start，lenth），若lenth为空就是一撸到底。
3. 用在string对象a上就可以a.(start,lenth)。

    bool check(string t,string s){//传递的是一个固定的最大公约数，并且只传递比较一次
        int lenx = (int)s.length() / (int)t.length();
        string ans = "";
        for (int i = 1; i <= lenx; ++i){
            ans = ans + t;
        }
        return ans == s;
    }
    string gcdOfStrings(string str1, string str2) {
        int len1 = (int)str1.length(), len2 = (int)str2.length();
        string T = str1.substr(0, __gcd(len1,len2)); /* __gcd() 为c++自带的求最大公约数的函数。leetcode的题解是这么说的，
        但我死活没调用出来__gcd（）函数，不过不是重点*/
        if (check(T, str1) && check(T, str2)) return T;
        return "";
    }

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/zi-fu-chuan-de-zui-da-gong-yin-zi-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最牛逼的！看蒙b数学系学生的数学法！


只要string1+string2==string2+string1 就行。

具体证明方法可以用切割法，string1+string2和string2+string1切成最大公因数大小的小块，然后由其各小块分别对应相等证明所有小块都相等，即可证明。

 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++自带的求最大公约数的函数
    }

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/zi-fu-chuan-de-zui-da-gong-yin-zi-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。