Dare2Solve
The problem asks to find the greatest common divisor (GCD) of two strings. Given two strings, str1
and str2
, the GCD of these strings is defined as the largest string X
such that X
can divide both str1
and str2
. A string X
divides another string Y
if Y
is constructed by concatenating X
multiple times.
The intuition behind solving this problem is similar to finding the GCD of two numbers. We start by identifying the common prefix of the two strings and check if this prefix can be the GCD string. The potential GCD string must divide both strings without leaving any remainder.
substr
to store potential GCD candidates.str1
and keep appending it to substr
.substr
, check if both str1
and str2
can be formed by repeating substr
:
substr
is removed.substr
, update the result with substr
.O(N * M), where N is the length of str1
and M is the length of str2
. We potentially check each substring of str1
and replace it in both str1
and str2
.
O(1) for the additional space used for the substring comparison, excluding the input strings.
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
string substr = "";
string result = "";
for (char i : str1) {
string newstr1 = str1;
string newstr2 = str2;
substr += i;
if (str1.find(substr) != string::npos) {
if (replaceAll(newstr1, substr) == "" && replaceAll(newstr2, substr) == "") {
result = substr;
}
} else {
return "";
}
}
return result;
}
private:
string replaceAll(string str, string substr) {
size_t pos;
while ((pos = str.find(substr)) != string::npos) {
str.erase(pos, substr.length());
}
return str;
}
};
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
substr = ""
result = ""
for i in str1:
newstr1 = str1
newstr2 = str2
substr += i
if str1.find(substr) != -1:
if newstr1.replace(substr, "") == "" and newstr2.replace(substr, "") == "":
result = substr
else:
return ""
return result
class Solution {
public String gcdOfStrings(String str1, String str2) {
String substr = "";
String result = "";
for (char i : str1.toCharArray()) {
String newstr1 = str1;
String newstr2 = str2;
substr += i;
if (str1.indexOf(substr) != -1) {
if (newstr1.replaceAll(substr, "").equals("") && newstr2.replaceAll(substr, "").equals("")) {
result = substr;
}
} else {
return "";
}
}
return result;
}
}
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var gcdOfStrings = function (str1, str2) {
let substr = "";
let result = "";
for (let i of str1) {
let newstr = str1;
newstr2 = str2;
substr = substr + i;
if (str1.indexOf(substr) !== -1) {
if (newstr.replaceAll(substr, "") === "" && newstr2.replaceAll(substr, "") === "") {
result = substr;
}
} else { return "" }
} return result;
}