算法练习-LeetCode1071. Greatest Common Divisor of Strings

 这道题一开没有想出来就直接放弃看别人的做法，看完之后才发现难怪自己想不粗来。真的不看别人的思路，直接看代码都看不懂😭。

参考的之后写的解题代码如下：

class Solution {
    public String OfStrings(String str1, String str2) {

        if(!(str1+str2).equals(str2+str1)){
            return "";
        }
        int  = getGcd(str1.length(),str2.length());

        return str1.substring(0,);
        
    }
    
    public int getGcd(int a , int b){
        if(b == 0) return a;
        return getGcd(b,a%b);
    }

}

思路：

（1）Corner Case：两个String 要有 Greatest Common Divisor（GCD）的话，左边右边拼接起来都应该是完全一样的，不能存在不同的情况：

"ABCEABCEABCE" + "ABCE" = "ABCEABCEABCEABCE"

"ABCE" + "ABCEABCEABCE" = "ABCEABCEABCEABCE"

如果存在不同的情况，就不存在最大GCD：

"ABAB" + "BB" = "ABABBB"

"BB" + "ABAB" = "BBABAB"

（2）存在GCD的情况下，如下其GCD的长度是两个String长度的最大公因子：

"ABCEABCEABCE" + "ABCE" = "ABCEABCEABCEABCE"

               12                        4                 ->      4 (最大公因子 = GCD长度)

"ABCE" + "ABCEABCEABCE" = "ABCEABCEABCEABCE"

通过递归找到GCD长度：

 public int getGcd(int a , int b){
        if(b == 0) return a;
        return getGcd(b,a%b);
    }

然后通过找到的GCD长度substring其中任意一个string就能找到GCD。