题目描述这题用到了gcd算法也就是欧几里得算法欧几里得算法的核心思想是两个数a和b的最大公约数等于b和a % b的最大公约数即gcd(a, b) gcd(b, a % b)。原理假设我们有两个数a和b其中a b如果a能被b整除即a % b 0则gcd(a, b) b。如果a不能整除b则通过a % b的余数将问题简化为新的两个数继续计算最大公约数gcd(a, b) gcd(b, a % b)。重复这个过程直到某次计算中b为 0返回a即为最大公约数。算法步骤初始化设定a和b。循环不断用较小的数去除较大的数直到余数为 0。返回值当余数为 0 时较大的数就是最大公约数。举个例子假设我们要求gcd(48, 18)。第一次计算48 % 18 12所以gcd(48, 18) gcd(18, 12)。第二次计算18 % 12 6所以gcd(18, 12) gcd(12, 6)。第三次计算12 % 6 0所以gcd(12, 6) 6。因此gcd(48, 18) 6。递归实现欧几里得算法可以用递归方式实现如下所示private int gcd(int a, int b) { if (b 0) { return a; // 如果b为0返回a即为最大公约数 } return gcd(b, a % b); // 否则递归调用 }题目解析如果两个字符串有公因子 abc那么 str1 就是 m 个 abc 的重复str2 是 n 个 abc 的重复连起来就是 mn 个 abc好像 mn 个 abc 跟 nm 个 abc 是一样的。所以如果 str1 str2 str2 str1 就意味着有解。当确定有解的情况下最优解是长度为gcd(str1.length, str2.length) 的字符串。代码class Solution { public String gcdOfStrings(String str1, String str2) { if(!(str1str2).equals(str2str1)){ return ; } return str1.substring(0,gcd(str1.length(),str2.length())); } private int gcd(int a,int b){ return b0?a:gcd(b,a%b); } }