What is the time complexity for the Repeated Substring Pattern problem?

The time complexity can vary. For the string concatenation approach, it is O(n), while the KMP approach also runs in O(n). More complex approaches might take longer.

How can I optimize my solution for the Repeated Substring Pattern problem?

Consider using KMP for efficient pattern matching, or the string concatenation method, which is simple and works well for most cases.

What is the pattern behind the Repeated Substring Pattern problem?

The problem follows the string matching pattern, where we try to identify repeating substrings within the string and check if they can construct the original string.

What edge cases should I consider for this problem?

Make sure to handle strings that are too short, non-repeating strings, and strings that might only seem to repeat a substring at first glance.

What are some variations of the Repeated Substring Pattern problem?

Variants could involve checking for a specific number of repetitions, finding the longest repeating substring, or working with multiple substrings forming the string.

#459

Easy

auto_awesomestring·结合·string·matching

LeetCode 题解工作台

重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。示例 1: 输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。示例 2: 输入: s = "aba" 输出: false 示例 3: 输入: s = "abcabcabcabc" 输出…

字符串字符串匹配

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 10⁴
s 由小写英文字母组成

lightbulb

解题思路

方法一：双倍字符串

若长度为 $n$ 的字符串 $s$ 由 $m$ 个重复子串组成，将 $s$ 拼接在自身上，得到字符串 $ss$ ，长度为 $2n$ ，此时若从下标 $1$ 开始查找 $s$ ，那么查找到的下标一定小于 $s$ 的长度。

若长度为 $n$ 的字符串 $s$ 不由重复子串组成，将 $s$ 拼接在自身上，得到字符串 $ss$ ，长度为 $2n$ ，此时若从下标 $1$ 开始查找 $s$ ，那么查找到的下标一定等于 $s$ 的长度。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return (s + s).index(s, 1) < len(s)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate is able to identify the pattern and suggest multiple methods for solving it.
question_mark
The candidate considers both the time and space complexity in their solution approach.
question_mark
The candidate explains string manipulation techniques clearly and concisely.

warning

常见陷阱

外企场景

error
The candidate might suggest overly complicated solutions when a simpler method, such as string concatenation, suffices.
error
Failing to account for edge cases like non-repeating strings or very short strings.
error
Overlooking the time complexity of the solution, especially when using nested loops or unnecessary operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if a string can be constructed from a substring with a limited number of repetitions.
arrow_right_alt
Determine the longest repeating substring that can form a string when repeated.
arrow_right_alt
Extend the problem to multiple substrings and check if they can collectively form the given string.

help

常见问题

外企场景

继续练习

#686 重复叠加字符串匹配 #214 最短回文串 #796 旋转字符串