Leetcode Note: Go - Greatest Common Divisor of Strings
Greatest Common Divisor of Strings - LeetCode
https://leetcode.com/problems/greatest-common-divisor-of-strings/
- Go 言語で取り組んだメモ
回答
Go 0ms O(n) solution - LeetCode Discuss
https://leetcode.com/problems/greatest-common-divisor-of-strings/discuss/489854/Go-0ms-O(n)-solution
func gcdOfStrings(str1 string, str2 string) string {
gcd := gcdOfInts(len(str1), len(str2))
for i := 0; i < gcd; i++ {
if str1[i] != str2[i] {
return ""
}
}
for i := range str1 {
if str1[i] != str1[i%gcd] {
return ""
}
}
for i := range str2 {
if str2[i] != str2[i%gcd] {
return ""
}
}
return str1[:gcd]
}
func gcdOfInts(x, y int) int {
if x < y {
x, y = y, x
}
for x % y != 0 {
x, y = y, x % y
}
return y
}