leetcode459. 重复的子字符串

题目描述

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

示例 1:

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

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

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

提示：

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/repeated-substring-pattern 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法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