技术问询：判断非空字符串是否由重复子串拼接而成

Hey there! Let's work through this Python interview problem together. The goal is to figure out if a given lowercase string can be built by repeating some substring multiple times. Let's break this down step by step.

Given a non-empty string consisting of only lowercase English letters (length ≤ 10000), check if it can be constructed by repeating a substring multiple times.

• Example 1: Input: "abab" → Output: True (formed by repeating "ab" twice)
• Example 2: Input: "aba" → Output: False (no single substring can be repeated to form it)

Approach 1: Brute Force (Intuitive but Less Efficient) #

The straightforward way is to check all possible substring lengths that divide the total length of the string. For each valid length k (where len(s) % k == 0), we take the first k characters as our candidate substring, then verify if repeating it len(s)//k times matches the original string.

Approach 2: Optimized String Concatenation Trick #

Here's a clever observation: if the string s is made by repeating a substring t, then concatenating s with itself (s+s) will contain s as a substring starting somewhere other than the first character. For example:

• s = "abab" → s+s = "abababab" — we can find "abab" starting at index 1 and 2
• s = "aba" → s+s = "abaaba" — the only occurrences of "aba" start at index 0 and 3, so trimming the first and last character ((s+s)[1:-1]) removes these exact matches, leaving no trace of s

This approach is concise and runs in near O(n) time (depending on the underlying string search implementation).

Code Implementations #

Brute Force Solution #

def repeatedSubstringPattern(s: str) -> bool:
    n = len(s)
    # Check all possible substring lengths from 1 to half the string length
    for k in range(1, n//2 + 1):
        if n % k == 0:
            # Repeat the candidate substring and compare to original
            if s[:k] * (n//k) == s:
                return True
    return False

Optimized String Concatenation Solution #

def repeatedSubstringPattern(s: str) -> bool:
    return s in (s + s)[1:-1]

Explanation #

• Brute Force: We iterate over feasible substring lengths. For each length that evenly divides the string's total length, we test if repeating the substring matches the original. This works but has a worst-case time complexity of O(n²) (like a string of all 'a's).
• Optimized Trick: By trimming the first and last character of s+s, we eliminate the exact start/end matches of s. If s is built from a repeated substring, there will still be another occurrence of s in this modified string. This is far more efficient and clean.

Test the Examples #

• For s = "abab": (s+s)[1:-1] = "bababa", which contains "abab" → returns True
• For s = "aba": (s+s)[1:-1] = "baab", which does not contain "aba" → returns False

内容的提问来源于stack exchange，提问作者casillas