1071. 字符串的最大公因子

小咪咪 2023-07-13 13:37 121阅读 0赞

# 题目： #

[1071. 字符串的最大公因子][1071.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解：求最大公约数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][2020031213194352.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

# 代码：求最大公约数 #

/** * code1071 */
    public class code1071 { 
    
        public static String gcdOfStrings(String str1, String str2) { 
            // 假设str1是N个x，str2是M个x，那么str1+str2肯定是等于str2+str1的。
            String s1 = str1 + str2;
            String s2 = str2 + str1;
            if (!s1.equals(s2)) { 
                return "";
            }
            int index = gcd(str1.length(), str2.length());
            return str1.substring(0, index);
        }
    
        // 辗转相除法求最大公约数 gcd
        public static int gcd(int a, int b) { 
            return b == 0 ? a : gcd(b, a % b);
        }
    
        public static void main(String[] args) { 
            String str1 = "ABCABC";
            String str2 = "ABC";
            String ans1 = gcdOfStrings(str1, str2);
            System.out.println(ans1);
    
            String str3 = "ABABAB";
            String str4 = "ABAB";
            String ans2 = gcdOfStrings(str3, str4);
            System.out.println(ans2);
    
            String str5 = "LEET";
            String str6 = "CODE";
            String ans3 = gcdOfStrings(str5, str6);
            System.out.println(ans3);
        }
    }

# 参考： #

1.  [字符串的最大公因子][Link 1]
2.  [1071. 字符串的最大公因子][1071. 1]
3.  [Java, 很简洁, 一眼就能看明白。][Java_ _]
4.  [Java 变量类型][Java]
5.  [Java substring() 方法][Java substring_]

[1071.]: https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200312131747341.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200312131906233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[2020031213194352.png]: https://img-blog.csdnimg.cn/2020031213194352.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200312132026751.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200312132051655.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200312132147293.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[Link 1]: https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/zi-fu-chuan-de-zui-da-gong-yin-zi-by-leetcode-solu/
[1071. 1]: https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/1071-zi-fu-chuan-de-zui-da-gong-yin-zi-by-wonderfu/
[Java_ _]: https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/java-hen-jian-ji-yi-yan-jiu-neng-kan-ming-bai-by-s/
[Java]: https://www.runoob.com/java/java-variable-types.html
[Java substring_]: https://www.runoob.com/java/java-string-substring.html