This is the 29th day of my participation in the August Wenwen Challenge.More challenges in August

Title description:

459. Repeated Substrings – LeetCode (leetcode-cn.com)

Given a non-empty string, determine whether it can be formed by repeating one of its substrings more than once. The given string contains only lowercase English letters and cannot exceed 10000 characters.

Example 1:

Input: "abab" Output: True Description: Can be formed by repeating the substring "ab" twice.Copy the code

Example 2:

Input: "ABA" output: FalseCopy the code

Example 3:

Input: "abcabcabcabc" Output: True Explanation: can be formed by repeating the substring "ABC" four times. (Or the substring "abcabc" is formed by repeating it twice.)Copy the code

Thought analysis

String matching

We join the two s’s together and remove the beginning and end elements. If s is a substring of the string, a duplicate substring exists.

AC code

class Solution {
    fun repeatedSubstringPattern(s: String): Boolean {
        val str = s + s
        return str.substring(1, str.lastIndex).contains(s)
    }
}
Copy the code
class Solution { 
    fun repeatedSubstringPattern(s: String): Boolean { 
        return (s+s).indexOf(s,1) != s.length 
    } 
}
Copy the code

The enumeration

A more general or violent solution

Let’s think about it, if a string can be made up of strings repeated more than once, then each time we delete the string from the string, we’re going to delete exactly the same thing.

Optimizations: If a string can be repeated multiple times, then it should be repeated at least twice. The maximum length of an arbitrary string is S.lenght /2, so we only need to loop up to 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}}Copy the code

conclusion

Read the solution, this problem is actually a typical KMP string matching problem, but THE KMP algorithm or before reading the time to see, now a little forgotten, review good next time to solve.

reference

459. Repeated Substrings – Repeated Substrings – LeetCode (leetcode-cn.com)

Thread – Repeated substrings – LeetCode (leetcode-cn.com)

Let’s do a cancellation algorithm here – repeated substrings – LeetCode (leetcode-cn.com)