459. Repeated Substring Pattern

2020, Dec 05 2 mins read

1. Description

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

2. Example

Example 1

Input: s = “abab”
Output: true
Explanation: It is the substring “ab” twice.

Example 2

Input: s = “aba”
Output: false

Example 3

Input: s = “abcabcabcabc”
Output: true
Explanation: It is the substring “abc” four times or the substring “abcabc” twice.

3. Constraints

1 <= s.length <= 10$^{4}$
s consists of lowercase English letters.

4. Solutions

Loop

n = str.size()
Time complexity: O($n^2$)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool repeatedSubstringPattern(const string &str) {
        cin.tie(nullptr);
        std::ios::sync_with_stdio(false);

        for (int i = 1; i <= str.size() / 2; ++i) {
            if (str.size() % i == 0) {
                bool match = true;
                for (int j = 0; j < i; ++j) {
                    for (int k = 1; j + k * i < str.size(); ++k) {
                        if (str[j + k * i] != str[j + (k - 1) * i]) {
                            match = false;
                            goto fast_quit;
                        }
                    }
                }
            fast_quit:
                if (match) {
                    return true;
                }
            }
        }

        return false;
    }
};

Search

Tags