字符串的最大公因子
#算法 #leetcode #算法/字符串
目录
题目
题目重点
- 最大公因子，能够除尽
思路
- 检查
str1 + str2是否等于str2 + str1。 不相等，说明没有公共前缀字符串，直接返回空字符串。 - 如果相等，找到
str1和str2长度的最大公约数（GCD）。 - 返回
str1的前G个字符。
代码实现
/*
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var gcdOfStrings = function (str1, str2) {
// 如果str1和str2的长度拼接不相等, 则返回空字符串
if (str1 + str2 !== str2 + str1) {
return "";
}
// 代码走到这里，说明 str1 和 str2 是符合条件的
// m 和 n 一定是有最大公约数的
const m = str1.length;
const n = str2.length;
const max = gcd(m, n); // 求最大公约数
return str1.substring(0, max); // 返回str1的前max个字符
};
/*
* 求最大公约数
* @param {number} a
* @param {number} b
* @return {number}
*/
var gcd = function (a, b) {
// a % b的结果赋值给a, b的值赋值给a, 直到b为0
// 为什么 b 为 0 时, a 就是最大公约数呢?
while (b !== 0) {
const temp = a % b;
a = b;
b = temp;
}
return a;
};