1071 Greatest Common Divisor of Strings 字符串的最大公因子
Description:
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:
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.
題目描述:
對于字符串 S 和 T肘交，只有在 S = T + ... + T（T 與自身連接 1 次或多次）時悠咱，我們才認定 “T 能除盡 S”涩禀。
返回字符串 X缺前，要求滿足 X 能除盡 str1 且 X 能除盡 str2严卖。
示例 :
示例 1：
輸入：str1 = "ABCABC", str2 = "ABC"
輸出："ABC"
示例 2：
輸入：str1 = "ABABAB", str2 = "ABAB"
輸出："AB"
示例 3：
輸入：str1 = "LEET", str2 = "CODE"
輸出：""
提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 為大寫英文字母
思路:
輾轉(zhuǎn)相除法, 如果兩個字符串有公因子, 那么 A + B一定等于 B + A
再利用輾轉(zhuǎn)相除法找到兩個字符串的長度的公因子即可
時間復(fù)雜度O(lgn), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
string gcdOfStrings(string str1, string str2)
{
return str1 + str2 == str2 + str1 ? str1.substr(0, gcd(str1.size(), str2.size())) : "";
}
private:
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
};
Java:
class Solution {
public String gcdOfStrings(String str1, String str2) {
return (str1 + str2).equals(str2 + str1) ? str1.substring(0, gcd(str1.length(), str2.length())) : "";
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
Python:
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
def gcd(a: int, b: int) -> int:
return a if b == 0 else gcd(b, a % b)
return str1[:gcd(len(str1), len(str2))] if str1 + str2 == str2 + str1 else ""
