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.

Repeated Substring Pattern — LeetCode 459 Python Solution

EasyStringString Matching

Problem: #459
Pattern: Hash Map
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

Python

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

Complexity

Measure	Complexity
Time	O(n)
Space	O(1) to O(n) auxiliary

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.

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.