1071. Greatest Common Divisor of Strings

Source

Revise GCD.

• Euclid’s Algorithm: This is an efficient and popular method for finding the GCD. It works as follows:
  1. Divide the larger number by the smaller number.
  2. Take the remainder of this division.
  3. If the remainder is 0, the smaller number is the GCD.
  4. Otherwise, repeat steps 1-3 using the smaller number and the remainder from the previous division.

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if((str1+str2).equals(str2+str1)){
            int gcd = gcdRecursive(str1.length(), str2.length());
            return str1.substring(0, gcd);
        } else{
            return "";
        }
    }
 
    public int gcdRecursive(int a, int b){
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public int gcdIterative(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}