Repeated Substring Pattern Problem
Description
LeetCode Problem 459.
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:
1
2
3
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.
Example 2:
1
2
Input: s = "aba"
Output: false
Example 3:
1
2
3
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
Constraints:
- 1 <= s.length <= 10^4
- s consists of lowercase English letters.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool repeatedSubstringPattern(string str) {
string nextStr = str;
int len = str.length();
if (len < 1) return false;
for (int i = 1; i <= len / 2; i++) {
if (len % i == 0) {
nextStr = leftShift(str, i);
if (nextStr == str) return true;
}
}
return false;
}
string leftShift(string &str, int l) {
string ret = str.substr(l);
ret += str.substr(0, l);
return ret;
}
};