# One line with RegEx

• ``````public class Solution {
public boolean repeatedSubstringPattern(String str) {
return str.matches("^([a-z]+)\\1+\$");
}
}
``````

Thanks to @StefanPochmann , it can be simplified:

``````public class Solution {
public boolean repeatedSubstringPattern(String str) {
return str.matches("(.+)\\1+");
}
}
``````

• Darn, why didn't I think of that. You can make it simpler, though: `return str.matches("(.+)\\1+");`

No need for `^` and `\$`, because `matches` tries to match the entire string anyway. And no need to explicitly name the characters.

• @StefanPochmann
Yes, you are right, it's simpler.

• nice solution!
But could you explain the time and space complexity?

• @saxion Uhhhhhh....
I don't know the time and space complexity of `matches()`...

• @ckcz123 For space complexity we might have to read the code, but for time complexity we could maybe find something out experimentally. Unless there's some optimization, strings like "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" are probably the worst case and probably handled by checking whether the string is "a" repeated and failing at the end, then checking whether it's "aa" repeated, etc. That would take quadratic time. So you could try different n and strings `"a" * (n-1) + "b"`, measure the runtimes and see whether that looks quadratic.

• @StefanPochmann

``````public class Main {
public static void main(String[] args){
long time=1;
for (int i=10000;i<=200000;i*=1.1) {
time = test(i, time);
}
}

static long test(int n, long last) {
char[] c=new char[n+1];
Arrays.fill(c, 'a');
c[n]='b';
String string=new String(c);
long start=System.currentTimeMillis();
string.matches("(.+)\\1+");
long time=System.currentTimeMillis()-start;
System.out.println(String.format("n = %d, time = %dms, time/last = %f", n, time, time/(last+0.0)));
return time;
}
}

n = 10000, time = 50ms, time/last = 50.000000
n = 11000, time = 25ms, time/last = 0.500000
n = 12100, time = 39ms, time/last = 1.560000
n = 13310, time = 38ms, time/last = 0.974359
n = 14641, time = 60ms, time/last = 1.578947
n = 16105, time = 54ms, time/last = 0.900000
n = 17715, time = 51ms, time/last = 0.944444
n = 19486, time = 87ms, time/last = 1.705882
n = 21434, time = 95ms, time/last = 1.091954
n = 23577, time = 115ms, time/last = 1.210526
n = 25934, time = 154ms, time/last = 1.339130
n = 28527, time = 123ms, time/last = 0.798701
n = 31379, time = 144ms, time/last = 1.170732
n = 34516, time = 170ms, time/last = 1.180556
n = 37967, time = 203ms, time/last = 1.194118
n = 41763, time = 245ms, time/last = 1.206897
n = 45939, time = 295ms, time/last = 1.204082
n = 50532, time = 357ms, time/last = 1.210169
n = 55585, time = 430ms, time/last = 1.204482
n = 61143, time = 518ms, time/last = 1.204651
n = 67257, time = 627ms, time/last = 1.210425
n = 73982, time = 758ms, time/last = 1.208931
n = 81380, time = 916ms, time/last = 1.208443
n = 89518, time = 1112ms, time/last = 1.213974
n = 98469, time = 1363ms, time/last = 1.225719
n = 108315, time = 1656ms, time/last = 1.214967
n = 119146, time = 1941ms, time/last = 1.172101
n = 131060, time = 2345ms, time/last = 1.208140
n = 144166, time = 2872ms, time/last = 1.224733
n = 158582, time = 3497ms, time/last = 1.217618
n = 174440, time = 4170ms, time/last = 1.192451
n = 191884, time = 5024ms, time/last = 1.204796
``````

• @ckcz123 Yes, looks quadratic. I ran it on my PC as well, though with `for (int i=10000; i<=500000; i*=Math.sqrt(2))` which gave me:

``````n = 10000, time = 21ms, time/last = 21.000000
n = 14142, time = 41ms, time/last = 1.952381
n = 19999, time = 38ms, time/last = 0.926829
n = 28282, time = 109ms, time/last = 2.868421
n = 39996, time = 189ms, time/last = 1.733945
n = 56562, time = 366ms, time/last = 1.936508
n = 79990, time = 716ms, time/last = 1.956284
n = 113122, time = 1439ms, time/last = 2.009777
n = 159978, time = 2865ms, time/last = 1.990966
n = 226243, time = 5728ms, time/last = 1.999302
n = 319955, time = 11532ms, time/last = 2.013268
n = 452484, time = 23253ms, time/last = 2.016389
``````

Of course there could be other strings that are still worse, but I do think "aaaaa...aaaaab" is worst case. So I do think O(n2) is correct.

For fun I also tried `c[0] = 'b';` which gave me:

``````n = 10000, time = 3ms, time/last = 3.000000
n = 14142, time = 2ms, time/last = 0.666667
n = 19999, time = 0ms, time/last = 0.000000
n = 28282, time = 0ms, time/last = NaN
n = 39996, time = 0ms, time/last = NaN
n = 56562, time = 16ms, time/last = Infinity
n = 79990, time = 4ms, time/last = 0.250000
n = 113122, time = 3ms, time/last = 0.750000
n = 159978, time = 2ms, time/last = 0.666667
n = 226243, time = 0ms, time/last = 0.000000
n = 319955, time = 5ms, time/last = Infinity
n = 452484, time = 6ms, time/last = 1.200000
``````

• @ckcz123 Could you briefly explain the regex you used in the code? I tested on regex.com, but it doesn't work. Thank you in advance!

• @Heronalps What does "it doesn't work" mean? You don't think any details would be helpful?

(For me it also doesn't work there, but that's because regex.com doesn't seem to exist.)

• @StefanPochmann Sorry for the typo, that was regexr.com. I entered both regular expression ^([a-z]+)\1+\$ and (.+)\1+ to test them by an example string (i.e. abcabcabc) in the textbox. But the regexr.com doesn't seem capture the string.

These two regex works in Java for sure, but, as a newbie to regex, I just like to understand the meaning of them. Thank you!

• @Heronalps Ok, I just tried that there, and it tells me that both of those regexes match that string (as they should). Are you sure that's exactly what you tested? If so, can you show a screenshot?

Edit: Saw that I can share it: http://regexr.com/3essk
Can you share yours that doesn't work?

• I think I figure it out. First, the escape character before backslash is not necessary @regexr.com. Second, ^ and \$ don't match strings in different lines probably because of the carriage return.