LeetCode.459 重复的子字符串

题目描述：

459. 重复的子字符串 - 力扣（LeetCode） (leetcode-cn.com)

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

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

思路分析

字符串匹配

我们将两个 s 连在一起，并去除首尾元素。如果 s 是该字符串的子串，则表明存在重复子串。

AC代码

class Solution {
    fun repeatedSubstringPattern(s: String): Boolean {
        val str = s + s
        return str.substring(1, str.lastIndex).contains(s)
    }
}

class Solution { 
    fun repeatedSubstringPattern(s: String): Boolean { 
        return (s+s).indexOf(s,1) != s.length 
    } 
}

枚举

通俗一点或者说是暴力解法

我们想下，如果一个字符串可以由字串重复多次构成，那么我们从这个字符串每次删掉这个字串，那么最后一定能正好删干净。

优化点： 如果一个字符串可以由字串重复多次构成，那么最少也要2次才叫重复，随意字串的最大长度为 s.lenght/2，因此我们循环只需要遍历到 n/2 即可

class Solution {
       fun repeatedSubstringPattern(s: String): Boolean {
        for (i in 1..s.length / 2) {
            if (s.length % i != 0) {
                continue
            }
            var tmp = s
            val key = s.substring(0, i)
            tmp = tmp.replace(key, "")
            if (tmp.isEmpty()) {
                return true
            }
        }
        return false
    }
}

总结

看了题解，这题其实算是一个典型的kmp字符串匹配问题，但是kmp算法还是之前看书的时候看到的，现在有点遗忘了，复习好下次再解。

参考

459. 重复的子字符串 - 重复的子字符串 - 力扣（LeetCode） (leetcode-cn.com)

思路 - 重复的子字符串 - 力扣（LeetCode） (leetcode-cn.com)

此处来个消消乐算法吧 - 重复的子字符串 - 力扣（LeetCode） (leetcode-cn.com)