Solution 2 – recursion
func gcdOfStrings(str1 string, str2 string) string {
// if str1 is made of str2 then str1+str2==str2+str1
// the resulting string looks like GCD of lengths of two strings
if str1+str2 != str2+str1 {
return ""
}
return str2[:gcd(len(str1),len(str2))]
}
func gcd(num1, num2 int) int {
if num1==0 {
return num2
}
if num1<num2{
num1, num2 = num2, num1
}
return gcd(num1-num2,num2)
}
Solution 1
func gcdOfStrings(str1 string, str2 string) string {
// in a loop check if they're equal upto min length else return empty
// loop over shortest string and build prefix in each run
// in an inner loop check if prefix holds up, if it does not break and continue building prefix
// save prefix if loop completes, clear it when breaking out of inner loop
// above logic does not work, gotta know GCD and euclids formula
// to be repeating by x combination of str1 and str2 should be equal else return empty
// return the string from 0 to GCD or lengths pf both strings
if str1+str2!=str2+str1{
return ""
}
return str1[:GCD(len(str1),len(str2))]
}
func GCD(a, b int) int {
for b != 0 {
t := b
b = a % b
a = t
}
return a
}
