素材下载平台网站源码,网站建站金融模板,合肥推广外包公司,可信赖的做网站Leetcode1071. 字符串的最大公因子 对于字符串 s 和 t#xff0c;只有在 s t … t#xff08;t 自身连接 1 次或多次#xff09;时#xff0c;我们才认定 “t 能除尽 s”。 给定两个字符串 str1 和 str2 。返回 最长字符串 x#xff0c;要求满足 x 能除尽 str1 且 x 能…Leetcode1071. 字符串的最大公因子 对于字符串 s 和 t只有在 s t … tt 自身连接 1 次或多次时我们才认定 “t 能除尽 s”。 给定两个字符串 str1 和 str2 。返回 最长字符串 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, str2.length 1000 str1 和 str2 由大写英文字母组成 方法一最大公因子法
分析
如果两个字符串有最大公因子那么str1str2和str2str1一定是一样的 比如例一str1 “ABCABC”, str2 “ABC” str1str2 和 str2str1 都是ABCABCABC 如果两个字符串没有最大公因子那么str1str2和str2str1一定不一样如果两个字符串有最大公因子那么str1str2他们的长度一定符合辗转相除法我们可以通过两个字符串的长度计算出他们最大公因子的长度 比如例一中str1的长度为6str2的长度为36和3的最大公因数是3输出的结果长度恰好是3然后通过计算出来的长度使用substring()截取出来即可 var gcdOfStrings function (str1, str2) {if (str1 str2 ! str2 str1) return // 如果不满足最大公因子的条件直接返回空字符串const gcd (a, b) (a % b 0 ? b : gcd(b, a % b))//辗转相除法return str1.substring(0, gcd(str1.length, str2.length))};运行结果 方法二暴力
这个效率比较慢主要是针对不满足条件的情况会比较浪费时间当然可以在前面加一个不满足条件的直接返回空来解决这个效率慢的问题
源码版
var gcdOfStrings function (str1, str2) {let factor str1.length str2.length ? str2 : str1;while (factor.length) {if (str1.split(factor).every(e e ) str2.split(factor).every(e e )) {return factor;}factor factor.slice(0, -1);}return
};解析版 var gcdOfStrings function (str1, str2) {let factor str1.length str2.length ? str2 : str1 //使用factor先存储str1和str2中的较短者// console.log(factor, factor)while (factor.length) {console.log(str1.split(factor), str1.split(factor))console.log(str2.split(factor), str2.split(factor))// 判断如果str1 和str2 都能被factor所分隔则这时的factor就是正确答案if (str1.split(factor).every(e e ) str2.split(factor).every(e e ) //split是将字符串根据传入的内容进行分隔存放到一个数组中 // abc.split(b)[a,c] abbbc.split(b) [a, , , c]// every是遍历数组中的每个元素如果都满足传入的函数的要求则返回true 否则false) {return factor}factor factor.slice(0, -1)//截取factor 每次删除factor字符串中的最后一个元素console.log(factor, factor)}return //如果循环结束了还没有返回则没有找到符合条件的factor 返回空字符串}console.log(gcdOfStrings(ABABAB, ABAB))console.log(abbbc.split(b));
运行结果 方法三暴力仿求最大公因子的辗转相除法
源码版
var gcdOfStrings function (str1, str2) {if (str1 str2 ! str2 str1) return return strGcb(str1, str2)}
function strGcb(a, b) {return (a.split(b).every(e e )) ? b : strGcb(b, a.split(b).filter(e { if (e ! ) { return e } }).join())
}解析版 var gcdOfStrings function (str1, str2) {if (str1 str2 ! str2 str1) return //首先判断str1 str2是否有最大公因数 return strGcb(str1, str2)}function strGcb (a, b) {return (a.split(b).every(e e )) ? b : strGcb(b, a.split(b).filter(e { if (e ! ) { return e } }).join())// a % b 0 ? b : isgy(b, a % b) 上一行代码是比着这个写出来的// a.split(b).every(e e )) 这个等价于 a%b0 // split是将字符串根据传入的内容进行分隔存放到一个数组中 // abc.split(b)[a,c] abbbc.split(b) [a, , , c]// every是遍历数组中的每个元素如果都满足传入的函数的要求则返回true 否则false// a.split(b).filter(e { if (e ! ) { return e } }).join() 等价于 a % b// filter() 遍历数组 得到满足条件的返回值 返回一个新数组 // join() 将数组的每一项 用传入的值作为分隔符 拼接成一个字符串}运行结果
