One line with RegEx


  • 7
    C
    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+");
        }
    }
    

  • 4

    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.


  • 0
    C

    @StefanPochmann
    Yes, you are right, it's simpler.
    I've updated on my answer.


  • 0
    S

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


  • 0
    C

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


  • 0

    @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.


  • 2
    C

    @StefanPochmann
    You are right, it's quadratic.

    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
    

  • 0

    @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
    

  • 0

    @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!


  • 0

    @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.)


  • 0

    @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!


  • 0

    @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?


  • 0

    @StefanPochmann 0_1481817547127_Screen Shot 2016-12-15 at 7.55.57 AM.png

    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.

    Thank you for contribution you made at Leetcode. Your answers frequently inspire me!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.