LeetCode 1071. 字符串的最大公因子

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

示例 1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

示例 2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

示例 3：
输入：str1 = "LEET", str2 = "CODE"
输出：""

提示：

1. 1 <= str1.length <= 1000
2. 1 <= str2.length <= 1000
3. str1[i] 和 str2[i] 为大写英文字母

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int length1 = str1.length(), length2 = str2.length();
        int g = gcd( length1, length2 );
        List<Integer> list = new LinkedList<>();
        for( int i = g; i >= 1; i-- ){
            if( length1 % i == 0 && length2 % i == 0 ){
                list.add(i);
            }
        }
        int index = 0;
        String res = ""; 
        while( index < list.size() ){
            boolean match = true;
            int len = list.get( index++ );
            String T = str1.substring( 0, len );
            for( int i = 0; i < length1 / len; i++ ){
                String tmp = str1.substring( i * len, i * len + len);
                if( T.equals(tmp) == false ) {
                    match = false;
                    break;
                }
            }
            for( int i = 0; i < length2 / len; i++ ){
                String tmp = str2.substring( i * len, i * len + len );
                if( T.equals(tmp) == false){
                    match = false;
                    break;
                }
            }
            if( match ){
                res = T;
                break;
            }
        }
        return res;
    }
    
    public int gcd( int a, int b ){  return b == 0 ? a : gcd( b, a % b ); }
}

运行结果，速度上可以