Algorithm
Problem Name: 1071. Greatest Common Divisor of Strings
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.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (str1.length() < str2.length()) {
return gcdOfStrings(str2, str1);
} else if (!str1.startsWith(str2)) {
return "";
} else if (str2.isEmpty()) {
return str1;
} else {
return gcdOfStrings(str1.substring(str2.length()), str2);
}
}
}
Input
str1 = "ABCABC", str2 = "ABC"
Output
"ABC"
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const gcdOfStrings = function(str1, str2) {
let res = "";
if (str1[0] !== str2[0]) return res;
if (str1[str1.length - 1] !== str2[str2.length - 1]) return res;
let s = str1[0];
let e = str1[str1.length - 1];
let loopStr = str1.length > str2.length ? str2 : str1;
for (let i = 1, len = loopStr.length; i < len; i++) {
if (loopStr[i] !== e) continue;
let tmp = loopStr.slice(0, i + 1);
let ok1 = false;
let ok2 = false;
let t1 = "";
let t2 = "";
while (t1.length < str1.length) {
t1 += tmp;
if (t1 === str1) {
ok1 = true;
break;
}
}
while (t2.length < str2.length) {
t2 += tmp;
if (t2 === str2) {
ok2 = true;
break;
}
}
if (ok1 && ok2 && tmp.length > res.length) res = tmp;
}
return res;
};
Input
str1 = "ABCABC", str2 = "ABC"
Output
"ABC"
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if len(str1) == len(str2):
return str1 if str1==str2 else ''
else:
if len(str1) < len(str2):
str1,str2 = str2,str1
if str1[:len(str2)] == str2:
return self.gcdOfStrings(str1[len(str2):],str2)
else:
return ''
Input
str1 = "ABABAB", str2 = "ABAB"
Output
"AB"
#4 Code Example with C# Programming
Code -
C# Programming
using System.Text;
namespace LeetCode
{
public class _1071_GreatestCommonDivisorOfStrings
{
public string GcdOfStrings(string str1, string str2)
{
if (str1 == str2) return str1;
if (str1.Length > str2.Length) return GcdOfStrings(str2, str1);
var i = 1;
while (i < = str1.Length)
{
var length = str1.Length / i;
if ((str1.Length % length == 0) && (str2.Length % length == 0))
{
var sb1 = new StringBuilder();
var sb2 = new StringBuilder();
var result = str1.Substring(0, length);
var x1 = str1.Length / length;
for (int j = 0; j < x1; j++)
sb1.Append(result);
var x2 = str2.Length / length;
for (int j = 0; j < x2; j++)
sb2.Append(result);
if ((str1 == sb1.ToString()) && (str2 == sb2.ToString()))
return result;
}
i++;
}
return string.Empty;
}
}
}
Input
str1 = "ABABAB", str2 = "ABAB"
Output
"AB"