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.
1
Example 1:
2
3
Input: str1 = "ABCABC", str2 = "ABC"
4
Output: "ABC"
5
Example 2:
6
7
Input: str1 = "ABABAB", str2 = "ABAB"
8
Output: "AB"
9
Example 3:
10
11
Input: str1 = "LEET", str2 = "CODE"
12
Output: ""
13
14
15
Note:
16
17
1 <= str1.length <= 1000
18
1 <= str2.length <= 1000
19
str1[i] and str2[i] are English uppercase letters.
Copied!
其實和最大公約數求法很近,可以先求兩個字串的長度,如果相等,直接比較字串是否相等;如果不相等,求出長度的倍數和餘數,然後比較整除部分是否是循環,如果不是則不存在最大公約數。如果是,將餘數拿來和較小的字串重新進行比較,得出最大公約數。 類似於輾轉相除法。
1
class Solution {
2
public:
3
string gcdOfStrings(string str1, string str2) {
4
if(str1.length()==str2.length()) return str1==str2?str1:"";
5
6
// cout<<str1.length() <<" "<< str2.length()<<endl;
7
if(str1.length()< str2.length()) swap(str1, str2);
8
9
int n=str1.length()/str2.length();
10
int m=str1.length()%str2.length();
11
// cout<<n<<" "<< m<< endl;
12
for(int i=1;i<n;i++)
13
{
14
for(int j=0;j<str2.length();j++)
15
{
16
if(str2[j]!=str1[j+i*str2.length()]) return "";
17
}
18
19
}
20
if(m==0) return str2;
21
return gcdOfStrings(str2,str2.substr(0,m));
22
23
24
25
}
26
};
Copied!
执行用时 :4 ms, 在所有 C++ 提交中击败了95.84%的用户 内存消耗 :8.9MB, 在所有 C++ 提交中击败了100%的用户
Copy link