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)