EasyNo. 0459
Repeated Substring Pattern — LeetCode 459 Python Solution
- Pattern
- Hash Map
- Topics
- String, String Matching
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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
- Input
- s = "abab"
- Output
- true
- Explanation
- It is the substring "ab" twice.
Python solution
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return (s + s).index(s, 1) < len(s)Complexity
- Time
- O(n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 459. Repeated Substring Pattern is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0214 | Shortest Palindrome | Hard |
| 0686 | Repeated String Match | Medium |
| 0796 | Rotate String | Easy |
| 1392 | Longest Happy Prefix | Hard |
| 1408 | String Matching in an Array | Easy |
| 2185 | Counting Words With a Given Prefix | Easy |
Frequently asked questions
- How hard is LeetCode 459. Repeated Substring Pattern?
LeetCode 459. Repeated Substring Pattern is rated Easy on LeetCode.
- What topics does LeetCode 459. Repeated Substring Pattern cover?
LeetCode 459. Repeated Substring Pattern is tagged String and String Matching on LeetCode.