1071.Greatest Common Divisor of Strings

1071.Greatest Common Divisor of Strings

难度:Easy

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 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] and str2[i] are English uppercase letters.

其實和最大公約數求法很近，可以先求兩個字串的長度，如果相等，直接比較字串是否相等；如果不相等，求出長度的倍數和餘數，然後比較整除部分是否是循環，如果不是則不存在最大公約數。如果是，將餘數拿來和較小的字串重新進行比較，得出最大公約數。 類似於輾轉相除法。

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {       
        if(str1.length()==str2.length()) return str1==str2?str1:"";

 //       cout<<str1.length() <<"   "<< str2.length()<<endl;
        if(str1.length()< str2.length()) swap(str1, str2);
        
            int n=str1.length()/str2.length();
            int m=str1.length()%str2.length();
       // cout<<n<<"   "<< m<< endl;
            for(int i=1;i<n;i++)
            {
                for(int j=0;j<str2.length();j++)
                {
                    if(str2[j]!=str1[j+i*str2.length()]) return "";
                }
                
            }
            if(m==0) return str2;
            return gcdOfStrings(str2,str2.substr(0,m));
        
        
        
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了95.84%的用户 内存消耗 :8.9MB, 在所有 C++ 提交中击败了100%的用户