Greatest Common Divisor of Strings - LeetCode
For two strings s and t, we say “t divides s” if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and 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: ""
Constraints:
1 <= str1.length, str2.length <= 1000str1andstr2consist of English uppercase letters.
解析
这个问题是找最大的相同分割字符，有点像最大公约数。写的时候大概分几个阶段，入果两个字符长度相等，判断是非相等，相等则为本身，否则是空。
其余情况，找到短的字符，先取第一个依次判断，接着取两个依次判断，接着三个，找到符合条件的。
预计这样算法复杂度略高。先解决问题再考虑其他。不要一上来就想用最优方法解决问题。
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
# 确定lstr为较长的字符串，sstr为较短的字符串
if len(str1) >= len(str2):
lstr, sstr = str1, str2
else:
lstr, sstr = str2, str1
# 如果lstr的长度是sstr的整数倍，尝试是否sstr * k == lstr
if len(lstr) % len(sstr) == 0:
if lstr == sstr * (len(lstr) // len(sstr)):
return sstr
# 否则从sstr中尝试找到可能的gcd字符串
for i in range(1, len(sstr)):
divisor = sstr[:len(sstr) - i]
if len(sstr) % len(divisor) == 0 and len(lstr) % len(divisor) == 0:
if sstr == divisor * (len(sstr) // len(divisor)) and lstr == divisor * (len(lstr) // len(divisor)):
return divisor
return ""
class Solution {
public String gcdOfStrings(String str1, String str2) {
String lstr;
String sstr;
lstr = str1.length() >= str2.length() ? str1 : str2;
sstr = str1.length() < str2.length() ? str1 : str2;
if (lstr.length() % sstr.length() == 0) {
if (lstr.equals(repeat(sstr, lstr.length() / sstr.length()))) {
return sstr;
}
}
for (int i = 1;i<sstr.length();++i){
String divisor = sstr.substring(0,sstr.length()-i);
if (lstr.length() % divisor.length() == 0 && sstr.length() % divisor.length() == 0){
if (sstr.equals(repeat(divisor, sstr.length()/divisor.length())) && lstr.equals(repeat(divisor, lstr.length() / divisor.length()))){
return divisor;
}
}
}
return "";
}
private String repeat(String s, int times) {
StringBuilder temp = new StringBuilder();
for (int i = 0;i<times;++i){
temp.append(s);
}
return temp.toString();
}
}
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
string lstr, sstr;
lstr = str1.size() >= str2.size() ? str1 : str2;
sstr = str1.size() < str2.size() ? str1 : str2;
if (lstr.size() % sstr.size() == 0){
if (lstr == repeatString(sstr, lstr.size() / sstr.size())){
return sstr;
}
}
for (int i = 1;i<sstr.size();++i) {
string divisor = sstr.substr(0, sstr.size() - i);
if (lstr.size() % divisor.size() == 0 && sstr.size() % divisor.size() == 0) {
if (sstr == repeatString(divisor, sstr.size() / divisor.size()) && (lstr == repeatString(divisor, lstr.size()/divisor.size()))){
return divisor;
}
}
}
return "";
}
private:
static std::string repeatString(const std::string& str, int times) {
std::string result;
for (int i = 0; i < times; ++i) {
result += str;
}
return result;
}
};
更多的方法
上面的内容是基础内容的重写，之后的部分是更快的方法。第一个好的思路是递归。大概的想法是先拿短的string去匹配长的相应的部分，匹配上继续把后面的部分当作新的string。直到结尾。
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if not str1 or not str2:
return str1 if str1 else str2
# If the combined strings are not equal, then there is no common divisor
if str1 + str2 != str2 + str1:
return ""
# If str1 starts with str2, then we might have a valid divisor
if str1.startswith(str2):
return self.gcdOfStrings(str1[len(str2):], str2)
# If str2 starts with str1, then we might have a valid divisor
if str2.startswith(str1):
return self.gcdOfStrings(str1, str2[len(str1):])
# Otherwise, no common divisor
return ""
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1.empty() || str2.empty()){
return str1.empty() ? str2 : str1;
}
if (str1 + str2 != str2 + str1){
return "";
}
if (str1.substr(0, str2.size()) == str2){
return this->gcdOfStrings(str1.substr(str2.size()), str2);
}
if (str2.substr(0, str1.size()) == str1){
return this->gcdOfStrings(str1, str2.substr(str1.size()));
}
return "";
}
};