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

绝地灬酷狼 2024-03-16 19:59 41阅读 0赞

题目来源  
[1768.字符串的最大公因子][1768.]

### 题目思路 ###

看见最大公因子就要想到gcd(辗转相除法)

public int gcd(int a,int b){
        
            return b == 0 ? a : (a % b);
        }

最大公因子的情况str1 + str2 == str2 + str1

*  题目已经给出:对于字符串 s 和 t，只有在 s = t + … + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
 *  如果不等于，那就没有最大公因子

本题还有一个注意点substring是左闭又开

### 解决方案 ###

class Solution {
        
        public String gcdOfStrings(String str1, String str2) {
        
            if(!(str1+str2).equals(str2+str1)){
        
                return "";
            }
            int index = gcd(str1.length(),str2.length());
            return str1.substring(0,index);
        }
    
        public int gcd(int a,int b){
        
            return b == 0 ? a : gcd(b,a % b);
        }
    }

![在这里插入图片描述][546871fa37fe459e972a0873d4c862c5.png]

[1768.]: https://leetcode.cn/problems/greatest-common-divisor-of-strings/
[546871fa37fe459e972a0873d4c862c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2f12bf2251ff41409215a0db7861047c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

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

题目来源 [1768.字符串的最大公因子][1768.] 题目思路看见最大公因子就要想到gcd(辗转相除法) public int gcd(int a,

绝地灬酷狼/ 2024年03月16日 19:59/ 0 赞/ 42 阅读

相关 LeetCode 字符串 179. 最大数

题目链接[https://leetcode.cn/problems/largest-number/description/][https_leetcode.cn_problem

悠悠/ 2024年03月02日 09:48/ 0 赞/ 52 阅读

相关 LeetCode_字符串_简单_1071.字符串的最大公因子

目录 1.题目 2.思路 3.代码实现（Java） 1.题目对于字符串 s 和 t，只有在 s = t + … + t（t 自身连接 1 次或

素颜马尾好姑娘i/ 2023年10月16日 09:09/ 0 赞/ 27 阅读

相关 1071. 字符串的最大公因子

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

电玩女神/ 2023年10月05日 19:52/ 0 赞/ 8 阅读

相关 LeetCode | 1071. Greatest Common Divisor of Strings字符串的最大公因子【Python】

> LeetCode 1071. Greatest Common Divisor of Strings字符串的最大公因子【Easy】【Python】【字符串】 Proble

ゞ浴缸里的玫瑰/ 2023年07月13日 15:08/ 0 赞/ 7 阅读

相关 1071. 字符串的最大公因子

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

小咪咪/ 2023年07月13日 13:37/ 0 赞/ 134 阅读

相关 LeetCode：1071.GreatestCommon（最大重复子串）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

「爱情、让人受尽委屈。」/ 2023年07月05日 14:52/ 0 赞/ 9 阅读

相关（C++）求最大公因子（辗转相除法）

具体算法也可以看这篇： [https://zhuanlan.zhihu.com/p/151447583][https_zhuanlan.zhihu.com_p_1514475

Bertha 。/ 2023年02月26日 06:19/ 0 赞/ 26 阅读

相关《数论概论》读书笔记第5章整除性与最大公因子数

这章就是讲最大公因子的一些概念和求gcd的方法。高中必修三，就已经知道可以有“辗转相除法”和“更相减损术”等方法能够更快的求出两个数的最大公因数讲述一些概念。

骑猪看日落/ 2022年06月13日 22:36/ 0 赞/ 308 阅读

相关【Leetcode】1071. Greatest Common Divisor of Strings（最大公约字符串）

For strings `S` and `T`, we say "`T` divides `S`" if and only if `S = T + ... + T` (`T`

朴灿烈づ我的快乐病毒、/ 2022年01月23日 04:39/ 0 赞/ 118 阅读