1071. Greatest Common Divisor of Strings

1. Brute Force

Intuition

모든 가능성이 있는 str을 최대공배수로 찾을 때까지 검수한다.
1. 두 str에 들어있는 공통적인 최대길이의 substr을 찾아낸다.
2. validation 검수를 통해 false를 반환 받는다면, 끝자리부터 조금씩 잘라낸다.

3. 유효성 검사

• if base is the GCD string, str1 and str2 are made up of multiples of base.
• check if the length of str is divisible by the length of base.

Algorithm

1. Find the shorter str among str1, str2, without loss of generality.
2. Check if both str1 and str2 are made of multiples of base.

• if so, return base
• Otherwise, we sheall try a shorter str by removing the last char from base.

3. If we have checked all prefix str without finding the GCD str, return empty str.

2. Greatest Common Divisor

1. GCD String에 대한 유효성 검증 방식

• base String이 있다면, str1, 2는 둘 다 base를 몇개 이어붙여 만든것이어야만 한다.

각각의 GCD를 구하고, 서로 str을 나눠봄
둘 다 나눠진다? 오우 셰 얘가 진짜 GCD임