Algorithm
Problem Name: 459. Repeated Substring Pattern
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 = "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.
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool repeatedSubstringPattern(char* str) {
int i, j, k;
int l = strlen(str);
for (i = 2; i < = l; i ++) {
if (l % i) continue;
k = l / i;
for (j = 1; j < i; j ++) {
if (strncmp(&str[0], &str[j * k], k)) break;
}
if (j == i) return true;
}
return false;
}
Input
s = "abab"
Output
true
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (int i = n / 2; i >= 1; i--) {
if (n % i == 0) {
int count = n / i;
StringBuilder sb = new StringBuilder();
String sub = s.substring(0, i);
while (count-- > 0) {
sb.append(sub);
}
if (sb.toString().equals(s)) {
return true;
}
}
}
return false;
}
}
Input
s = "abab"
Output
true
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const repeatedSubstringPattern = function(s) {
const len = s.length
let tmp = ''
for(let i = 1; i < = len; i++) {
tmp = s.substr(0, i)
if (tmp.length === len) {
return false
}
if (s === genStr(tmp, len)) {
return true
}
}
return false
};
function genStr(sub, limit) {
let str = sub
while(str.length < limit) {
str += sub
}
return str
}Input
s = "aba"
Output
false
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def repeatedSubstringPattern(self, s):
"""
:type s: str
:rtype: bool
"""
return True if len(s)>1 and (s in [s[:i]*(len(s)//i) for i in range(2,len(s)) if len(s)%i==0] or s==s[0]*len(s)) else False
Input
s = "aba"
Output
false
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0459_RepeatedSubstringPattern
{
public bool RepeatedSubstringPattern(string s)
{
var N = s.Length;
var dp = new int[N];
for (int i = 1; i < N; i++)
{
int j = dp[i - 1];
while (j > 0 && s[j] != s[i])
j = dp[j - 1];
if (s[i] == s[j])
j++;
dp[i] = j;
}
return dp[N - 1] > 0 && N % (N - dp[N - 1]) == 0;
}
}
}
Input
s = "abcabcabcabc"
Output
true