LeetCode 1071 - Greatest Common Divisor of Strings

Algorithm

LeetCode 1071 - Greatest Common Divisor of Strings

쿠케캬캬 2023. 2. 1. 21:49

https://leetcode.com/problems/greatest-common-divisor-of-strings/

Greatest Common Divisor of Strings - LeetCode

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

leetcode.com

두 문자열 a와 b가 있을 때, a + b != b + a 라면 gcd가 없습니다.(a + b = n*gcd + m*gcd = b + a)

그렇지 않다면, 두 문자열의 최대공약수 길이의 문자열이 gcd가 될 수 있습니다.

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if(str1 + str2 != str2 + str1) return "";
        return str1.substr(0, gcd(str1.size(), str2.size()));
    }
};