[Array/String][Easy] 1071. Greatest Common Divisor of Strings
Greatest Common Divisor of Strings - LeetCode
Can you solve this real interview question? 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 t
leetcode.com
Q. str1과 str2가 주어질때, 두 string을 공통으로 나누는 base String이 존재한다. 이 base string의 최대를 구하라.
두 string을 baseStr이 동시에 나눈다고 했으므로,
str1 = baseStr +.. + baseStr;
str2 = baseStr + ... + baseStr;
인 것이다.
따라서 두 수에 공통반복이 존재하므로,
str1 + str2 == str2 + str1 이어야 한다.
이 조건을 만족하면, 서로 문자안에 공통 string으로 구성된 문장들이라는 조건이 만족한다.
이 중에 가장 큰 녀석을 찾는다.
서로 동일 반복 string의 집합이므로, 이는 두 string의 length에 대한 최대공약수값과 일치하게 된다.
string gcdOfStrings(string str1, string str2)
{
// str1가 str2로 나눠지는 최대 string을 찾아라.
if (str1 + str2 != str2 + str1)
return "";
int iGCD = gcd(str1.length(), str2.length());
return str1.substr(0, iGCD);
}
Difficulty : Easy
Key : Algorithm
Time complexity : O(m+n)
string덧붙이고 같은지 확인하는 연산에 O(m+n) 소요.
GCD 함수 자체는 유클리드알고리즘을 사용하여 log(mxn) 따라서 최종 O(m+n)
Space complexity : O(m+n) - 덧붙이는 연산에 의하여.
Comment : 풀이법(알고리즘)을 모르면 hard고 알면 easy다.....