题目
459. 重复的子字符串
简单
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba" 输出: false
示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 104s由小写英文字母组成
思路和解题方法
- 首先，将输入字符串
s加上自身得到新的字符串t，即t = s + s。- 然后，使用
erase()函数对t进行处理，将首尾两个字符删掉，即t.erase(t.begin()); t.erase(t.end() - 1);。这样做是为了去除t中重复字符串的一部分，从而只保留完整的重复字符串。- 接下来，使用
find()函数在字符串t中查找子字符串s。如果找到了子字符串s，即t.find(s) != std::string::npos，则返回true表示字符串由重复的子字符串构成。- 如果没有找到子字符串
s，说明字符串不是由重复的子字符串构成，则返回false。
复杂度
时间复杂度:
O(n)
- 字符串的拼接操作需要花费O(n)的时间，其中n是字符串的长度。
- 字符串的擦除操作也需要花费O(n)的时间，其中n是字符串的长度。
- 字符串的查找操作使用了
find()函数，其时间复杂度为O(n)，其中n是被查找字符串的长度。
空间复杂度
O(n)
- 空间复杂度是O(n)，其中n是输入字符串的长度。主要是为了存储临时变量
t，其长度为输入字符串s的两倍。
c++ 代码
class Solution {
public:bool repeatedSubstringPattern(string s) {string t = s + s; // 将字符串s拼接成t，长度为2 * s.length()t.erase(t.begin()); t.erase(t.end() - 1); // 去掉t的首尾字符，保留完整的重复字符串if (t.find(s) != std::string::npos) // 在t中查找sreturn true; // 如果找到了s，说明字符串是由重复的子字符串构成return false; // 如果没有找到s，说明字符串不是由重复的子字符串构成}
};
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
