重复的子字符串

1.题目

459. 重复的子字符串 - 力扣（LeetCode）

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2:

输入: “aba”
输出: False

示例 3:

输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

题目模板

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {

};

2.思路分析

见题解

3.所用到的方法

• 正则表达式 - JavaScript | MDN
• 正则表达式在线测试 - 站长工具

4.题解及优化

课程解法

var repeatedSubstringPattern = function (s) {
  return /^(\w+)\1+$/.test(s)
}

• ^：正则匹配开始
• (\w+)
• • ()：小括号表示捕获并记住
  • \w：匹配字母或数字或下划线
  • +：匹配多次
• \1+：返回最后的第1+个子捕获匹配的子字符串(捕获的数目以左括号计数)
• $：正则匹配结束
  

其他小伙伴的解法

字符串includes

假设字符串由 n 个相同子串组成, 重复、掐头去尾后包含子串 2n - 2, 如果仍然包含原字符串即 2n - 2 > n,那就表示 n > 2

var repeatedSubstringPattern = function(s) {
  return (s + s).slice(1, -1).includes(s)
}

周期解法

周期串为s, 那么设定t表示最小周期, 数学中周期的表达式是

f(x+t)=f(x)

字符串中 ​s = item * count
那么我们需要找到最小周期 t = item.length

var repeatedSubstringPattern = function(s) {
  let len = s.length
  let i = 1
  while (i <= len / 2) {
    if (len % i === 0 && s.slice(0, i).repeat(len / i) === s) {
      return true
    }
    i++
  }
  return false
};