0459. Repeated Substring Pattern¶
题目信息¶
- 题号:
0459
- 难度:
Easy
- 主题:
小写字符串、非空子串、完整重复、模式判断
- 原题:
- 重点:
基本子串必须比原串短、从头到尾连续重复至少两次、不能遗漏或重排字符
题目重述¶
给定只包含小写英文字母的非空字符串 s,判断是否存在一个非空且长度小于 s 的字符串 t,使 s 恰好由 t 连续重复若干次组成。
重复次数必须至少为 2,所有字符都必须被完整覆盖,不能只让某个前缀或子串满足重复关系。s.length 位于 [1, 10^4]。
自建示例¶
同一模式重复三次:
输入:s = "abcabcabc"
输出:true
解释:字符串可由非空子串 abc 连续重复 3 次得到。
前后局部相似但不能完整重复:
输入:s = "abac"
输出:false
解释:不存在一个较短子串能够从头到尾重复并恰好覆盖全部四个字符。
利用重复串的旋转性质¶
若 s 由某个更短模式重复组成,那么把 s 与自身拼接后,除去最左和最右的一个完整边界,仍会在中间找到一次完整的 s。反过来,若 s 在 (s+s) 的位置 1 之后再次出现,这个出现位置提供的周期会把原串分解为至少两段相同模式。
长度为 1 的字符串必须排除,因为它的双倍串从位置 1 也能找到自身,但不存在更短的非空模式。
C++ 实现¶
class Solution {
public:
bool repeatedSubstringPattern(std::string s) {
if (s.size() <= 1) return false;
std::string doubled = s + s;
return doubled.find(s, 1) != s.size();
}
};
代码分析¶
从位置 1 开始查找并排除末尾位置 s.size() 的原始副本,只有中间再次出现才说明存在严格更短的周期。该实现依赖标准字符串查找,空间复杂度为 O(n);若按库实现的查找复杂度计,时间不超过常见的 O(n^2),也可由线性匹配算法优化到 O(n)。