【Leetcode】1071. Greatest Common Divisor of Strings（最大公约字符串）

朴灿烈づ我的快乐病毒、 2022-01-23 04:39 118阅读 0赞

For strings `S` and `T`, we say "`T` divides `S`" if and only if `S = T + ... + T` (`T` concatenated with itself 1 or more times)

Return the largest string `X` such that `X` divides str1 and `X` divides 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: ""

**Note:**

1.  `1 <= str1.length <= 1000`
2.  `1 <= str2.length <= 1000`
3.  `str1[i]` and `str2[i]` are English uppercase letters.

题目大意：

给出两个字符串，找出最大的“公约”字符串，即这个字符串可以将str1和str2分成整数等分。

解题思路：

找出两个字符串的“最小周期串”，比较两个周期串是否相同，如果相同进一步判断将最小周期串复制多份之后长度是否能够同时被str1和str2的长度整除，输出最大的一个。

class Solution {
    private:
    int help(string s){
        int i, j, flag=1;//i记录周期长度,j记录从第二个周期开始字符的位置
    	    int len = s.length();//len为字符串长度
    	    for(i=1; i <= len; i++)
    		if(len%i == 0)//字符串的长度一定可以被周期整除
    		{
    			flag = 1;
    			//检测 字符串是否具有周期性
    			for(j=i; j<len; j++)//str[i]为第二周期的第一个字符
    			{
    				if(s[j] != s[j%i])
    				{
    					flag = 0;
    					break;
    				}
    			}
    			if(flag)//找到周期跳出
    				break;
    		}
        return i;
    }
    bool valid(string s1, string s2, string a1,int i){
        if(s1.length()%(a1.length()*i)==0&&s2.length()%(a1.length()*i)==0){
            return true;
        }
        return false;
    }
    public:
        string gcdOfStrings(string str1, string str2) {
            string ans;
            int l1 = str1.length();
            int l2 = str2.length();
            if(l2 == l1){
                if(str1==str2) return str1;
                else return ans;
            }
            if(l1<l2){
                string tmp_s;
                tmp_s = str2;
                str2 = str1;
                str1 = tmp_s;
                int aa=l1;
                l1=l2;
                l2 = aa;
            }
            
            
            int s1,s2;
            s1 = help(str1);
            s2 = help(str2);
            string a1, a2;
            a1.assign(str1,0,s1);
            a2.assign(str2,0,s2);
            if(a1!=a2) return ans;
            if(s2==l2) return a2;
            int max_time = 0; 
            for(int i=1;i<=l2/s1;i++){
                if(valid(str1,str2,a1,i)){
                    max_time = max(max_time, i);
                }
            }
            while(max_time--){
                ans+=a1;
            }
            
            return ans;
        }
    };