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%的用户