晋江建设银行招聘网站,惠州网站建设如何,wordpress盗版,wordpress 分类 标题题目
459. 重复的子字符串
简单
给定一个非空的字符串 s #xff0c;检查是否可以通过由它的一个子串重复多次构成。 示例 1:
输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。示例 2:
输入: s aba
输出: false示例 3: …题目
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说明字符串不是由重复的子字符串构成}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
