459. Repeated Substring Pattern
1. Description
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
2. Example
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.
3. Constraints
- 1 <= s.length <= $10^4$
- s consists of lowercase English letters.
4. Solutions
Loop
n = str.size()
Time complexity: O($n^2$)
Space complexity: O(1)
class Solution {
public:
bool repeatedSubstringPattern(const string &str) {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
for (int i = 1; i <= str.size() / 2; ++i) {
if (str.size() % i == 0) {
bool match = true;
for (int j = 0; j < i; ++j) {
for (int k = 1; j + k * i < str.size(); ++k) {
if (str[j + k * i] != str[j + (k - 1) * i]) {
match = false;
goto fast_quit;
}
}
}
fast_quit:
if (match) {
return true;
}
}
}
return false;
}
};