🥉Easy

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

示例 1**:

  1. 输入: "abab"
  2. 输出: True
  3. 解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

  1. 输入: "aba"
  2. 输出: False

示例 3:

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

题解

正常的思路

这道题还是很简单的，从头开始遍历字符串，如果子串的长度可以被字符串整除，而且整个字符串等于子串*(字符串长度/子串长度)，就说明子串可以重复构成字符串

Python

  1. class Solution:
  2.     def repeatedSubstringPattern(self, s: str) -> bool:
  3.         length = len(s)
  4.         for i in range(1,length):
  5.             t=s[0:i]
  6.             if length%len(t)==0 and t*(length//len(t)) == s:
  7.                 return True
  8.             else:
  9.                 continue
  10.         return False

JavaScript

var repeatedSubstringPattern = function(s) {
    let len = s.length;
    for (let t = 1; t <= len / 2; t++) {
        const item = s.slice(0, t);
        const count = len / item.count;
        if (Number.isInteger(count) && item.repeat(count) === s) {
            return true
        }
    }
    return false
};

巧解

为了避免这种无用的环绕，可以创建一个新的字符串str,它等于原来的字符串S再加上S自身，这样其实就包含了所有移动的字符串。

比如字符串：S = acd，那么str = S + S = acdacd

acd移动的可能：dac、cda。其实都包含在了str中了。就像一个滑动窗口

一开始acd (acd) ，移动一次ac(dac)d,移动两次a(cda)cd。循环结束

所以可以直接判断str中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。

/**
• @param  {string} s 
• @return  {boolean} 
*/
var repeatedSubstringPattern = function(s) {
    let s1 = (s + s).slice(1, -1);
    return s1.indexOf(s) != -1;
};