leetcode459. 重复的子字符串

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。 示例 2:

输入: s = "aba" 输出: false 示例 3:

输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 104 s 由小写英文字母组成

解题思路

法1

双指针法:

1. 循环是由首字母开始的我们只需要找到字符串之后的首字母的位置开始做循环判断,
2. 如果中途失败,就重新做下一个首字母的循环判断,直到无法判断循环或者成功的时候返回结果

时间复杂度(O(n)) 空间复杂度(O(1))

执行结果

法1

func repeatedSubstringPattern(s string) bool {
          
       length := len(s)     for i := 1; i <= length/2; i++ {
          
           if length%i == 0 {
          
               sub := s[:i]             repeat := length / i             isRepeated := true             for j := 1; j < repeat; j++ {
          
                   if s[j*i:(j+1)*i] != sub {
          
                       isRepeated = false                     break                 }             }             if isRepeated {
          
                   return true             }         }     }     return false }

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 8 ms , 在所有 Go 提交中击败了 48.79% 的用户 内存消耗： 4.2 MB , 在所有 Go 提交中击败了 73.97% 的用户 通过测试用例： 129 / 129