LeetCode link: 459. Repeated Substring Pattern, difficulty: Easy.
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 1:
Input: s = "abcabcabcabc"
Output: true
Explanation:
It is the substring "abc" four times or the substring "abcabc" twice.
Example 2:
Input: s = "aba"
Output: false
Constraints:
1 <= s.length <= 10000sconsists of lowercase English letters.
Intuition
Webmaster (Zhang Jian): π
Hi everyone! I am Zhang Jian.
I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed
leader.me!
π leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.
The key to solving this problem is to see clearly that if s can be obtained by repeating the substring, then the starting letter of the substring must be s[0].
Once you understand this, the scope of substring investigation is greatly narrowed.
Complexity
Time complexity
O(N * N)
Space complexity
O(N)
Python #
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
for i in range(1, int(len(s) / 2) + 1):
if len(s) % i == 0 and s[:i] * int(len(s) / i) == s:
return True
return False
JavaScript #
var repeatedSubstringPattern = function (s) {
for (let i = 1; i <= s.length / 2; i++) {
if (s.length % i != 0) {
continue
}
if (s.slice(0, i).repeat(s.length / i) == s) {
return true
}
}
return false
};
Go #
func repeatedSubstringPattern(s string) bool {
n := len(s)
for i := 1; i <= n/2; i++ {
if n%i == 0 {
substring := s[:i]
repeated := strings.Repeat(substring, n/i)
if repeated == s {
return true
}
}
}
return false
}
C++ #
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.length();
for (int i = 1; i <= n / 2; i++) {
if (n % i != 0) {
continue;
}
string pattern = s.substr(0, i);
string repeated = "";
for (int j = 0; j < n / i; j++) {
repeated += pattern;
}
if (repeated == s) {
return true;
}
}
return false;
}
};
Java #
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (var i = 1; i <= n / 2; i++) {
if (n % i != 0) {
continue;
}
var pattern = s.substring(0, i);
var repeated = new StringBuilder();
// Simply concatenate the pattern multiple times
for (var j = 0; j < n / i; j++) {
repeated.append(pattern);
}
// Compare the constructed string with the original string
if (repeated.toString().equals(s)) {
return true;
}
}
return false;
}
}
C# #
public class Solution
{
public bool RepeatedSubstringPattern(string s)
{
int n = s.Length;
for (int i = 1; i <= n / 2; i++)
{
if (n % i != 0)
{
continue;
}
// Get the potential substring pattern
string pattern = s.Substring(0, i);
StringBuilder repeated = new StringBuilder();
// Simply concatenate the pattern multiple times
for (int j = 0; j < n / i; j++)
{
repeated.Append(pattern);
}
// Compare the constructed string with the original string
if (repeated.ToString() == s)
{
return true;
}
}
return false;
}
}
Ruby #
# @param {String} s
# @return {Boolean}
def repeated_substring_pattern(s)
(0...s.size / 2).each do |i|
next unless s.size % (i + 1) == 0
if s[0..i] * (s.size / (i + 1)) == s
return true
end
end
false
end
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 459. Repeated Substring Pattern. Thanks!Level Up Your Developer Identity
π While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend leader.me β the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- π Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
- π Free Custom Domain: Bind your own personal domain for freeβforever.
- β¨ Premium Subdomains: Stand out with elite tech handle like
name.leader.me.