1071. Greatest Common Divisor of Strings

Naive

```java
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        if (len1 == len2) {
            if (str1.equals(str2)) {
                return str1;
            } else {
                return "";
            }
        }
        String result = "";
        if (len1 > len2) {
            result = helper(str1, str2);
        } else {
            result = helper(str2, str1);
        }
        return result;
    }
    private String helper(String s1, String s2) {
        for (int i = s2.length(); i >= 1; i--) {
            String subStr = s2.substring(0, i);
            String temp1 = new String(s1);
            String temp2 = new String(s2);
            temp1 = temp1.replace(subStr, "");
            temp2 = temp2.replace(subStr, "");
            //System.out.println("subStr:" + subStr + "temp:" + temp);
            if (temp1.isEmpty() && temp2.isEmpty()) {
                return subStr;
            }
        }
        return "";
    }
}

/**

 */
```

GCD

```java
因為一開始就排除了沒有 gcd string 的 case

所以剩下的都是有 gcd string的, 所以我們就可以取最大公因數的長度就可以了！ （求的是 max common divisor string)
為什麼可行？ 反問自己, 那為什麼數字就可以呢？ （關鍵還是一開始排除了非的狀況啦...

T: O(m+n)
S: O(m+n)
```

```java
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2+str1)) {
            return "";
        }
        int gcdStringIndex = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdStringIndex);
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
}
/**
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b); // 5,3, -> 3, 1 -> 1, 3%1 = 0
        // 6,2 -> gcd(2, 0) -> 2
    }
 */
```