最新：2020.3 字符串的最大公因子

港控/mmm° 2023-07-13 15:24 26阅读 0赞

### 描述： ###

> 题库链接：[https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/][https_leetcode-cn.com_problems_greatest-common-divisor-of-strings]
> 
> 对于字符串 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 <= str1.length <= 1000  
> 1 <= str2.length <= 1000  
> str1\[i\] 和 str2\[i\] 为大写英文字母

### 自我解题思路： ###

class Solution {
        public String gcdOfStrings(String str1, String str2) {
            int len1 = str1.length();
            int len2 = str2.length();
            String subStr = "";
            int count = 0;
            while (count < len2 && len1 > 0 && len2 > 0) {
                subStr = str2.substring(count);
                int subLength = subStr.length();
                if (len1 % subLength == 0 && len2 % subLength == 0) {
                    len1 = str1.replaceAll(subStr, "").length();
                    len2 = str2.replaceAll(subStr, "").length();
                    if (len1 == 0 && len2 == 0) {
                        return subStr;
                    }
                }
                count++;
            }
            return "";
        }
    }

### 大佬思维： ###

class Solution {
        public String gcdOfStrings(String str1, String str2) {
            // 假设str1是N个x，str2是M个x，那么str1+str2肯定是等于str2+str1的。
            if (!(str1 + str2).equals(str2 + str1)) {
                return "";
            }
            // 辗转相除法求gcd。
            return str1.substring(0, gcd(str1.length(), str2.length()));
        }
    
        private int gcd(int a, int b) {
            return b == 0? a: gcd(b, a % b);
        }
    }

[https_leetcode-cn.com_problems_greatest-common-divisor-of-strings]: https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/