LeetCode-in-Java
459. Repeated Substring Pattern
Easy
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1:
Input: s = “abab”
Output: true
Explanation: It is the substring “ab” twice.
Example 2:
Input: s = “aba”
Output: false
Example 3:
Input: s = “abcabcabcabc”
Output: true
Explanation: It is the substring “abc” four times or the substring “abcabc” twice.
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.
Solution
public class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
if (n < 2) {
return false;
}
int i = 0;
while (i < (n + 1) / 2) {
if (n % (i + 1) != 0) {
i++;
continue;
}
boolean match = true;
String substring = s.substring(0, i + 1);
int skippedI = i;
for (int j = i + 1; j < n; j += i + 1) {
if (!s.substring(j, j + i + 1).equals(substring)) {
match = false;
break;
}
skippedI += i + 1;
}
if (match) {
return true;
}
i = skippedI;
i++;
}
return false;
}
}