Easy and fast Python


  • 2
    def repeatedSubstringPattern(self, s):
        n = len(s)
        return any(n / d * s[:d] == s
                   for d in range(1, n)
                   if n % d == 0)
    

    I just try all possible divisors. Submitted three times, accepted in 78, 68 and 89 ms, average 78.3 ms.

    Here's an optimized version, accepted in 39, 62 and 45 ms, average 48.7 ms.

    def repeatedSubstringPattern(self, s):
        n = len(s)
        d = 1
        while d * d <= n:
            if n % d == 0:
                for m in {d, n/d}:
                    if m > 1 and m * s[:n/m] == s:
                        return True
            d += 1
        return False
    

    For comparison, I also tested @protein-graph's KMP O(n) solution (the only Python solution posted so far) which got accepted in 185, 235 and 185 ms, average 201.7 ms.

    The baseline (the time not caused by our solution but by the judge) is about 38 ms, as determined by the below cheat which got accepted in 42, 33 and 39 ms. Subtracting that, my solutions averaged 40.3 ms and 10.7 ms, and @protein-graph's averaged 163.7 ms.

    class Solution(object):
        answers = [False, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False, False, False, False, False, False, False, False, False, False, True, True, True, False, False, False, False, False, False, False, False, False, False, False, False, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False, True, False, False, False, False, False, False, True, False, False, True, True, True, True, True, False, True, False, True, False, True]
        def repeatedSubstringPattern(self, s):
            return self.answers.pop()
    

    Just another way to write my optimized solution:
    def repeatedSubstringPattern(self, s):
        n = len(s)
        return any(m > 1 and m * s[:n/m] == s
                   for d in range(1, int(n**0.5+2))
                   if n % d == 0
                   for m in {d, n/d})
    

    Got accepted in 45, 38 and 72 ms.


  • 0
    P

    Thank you so much for your optimized code. I am still learning and was just wondering, we'd think checking all divisors and comparing strings should be O(n**2) while just one pass KMP should be O(n), but clearly numbers indicate this approach is better.

    Anyway KMP approach could have been coded better to actually reflect O(n) performance?


  • 1

    @protein.graph said in Easy and fast Python:

    checking all divisors and comparing strings should be O(n**2)

    Not just O(n2) but also O(n1.5). And possibly better, though I haven't been able to find out. But I know for numbers up to 10000, I'm trying only up to 63 divisors. And the largest number causing that many divisors is 9240. Which is why many of the judge's test strings have that length.

    Anyway KMP approach could have been coded better to actually reflect O(n) performance?

    I don't understand the KMP approach yet, but it really should be O(n) and then it does "reflect O(n) performance", no? Or do you think what you wrote isn't O(n)? Not sure what you're saying.

    Anyway... I believe the reason my solution is faster is that string multiplication and string comparison are (1) very simple and (2) done in C.


Log in to reply
 

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