1 line in Python


  • 9
    class Solution(object):
        def repeatedSubstringPattern(self, s):
            return any(s[:i] * (len(s) / i) == s for i in range(1, len(s)) if len(s) % i == 0)
    

    Time complexity is O(n1.5) because I do for O(n0.5) times (number of divisors of n) an O(n) operation, i.e., s[:i] * (len(s) / d) == s. Space complexity is O(n).


  • 0

    Where is d?


  • 0

    Should replace d by i and stop by len(s) / 2 + 1.

    class Solution(object):
        def repeatedSubstringPattern(self, s):
            return any(s[:i] * (len(s) / i) == s for i in range(1, len(s) / 2 + 1) if len(s) % i == 0)
    

  • 1

    @agave Concise 1-line solution! Actually, if you could check both d and len(s)/d in the loop, you could cut the range to be [1, sqrt(len(s))] since all divisors in [sqrt(len(s)), len(s)/2] can be derived from previous range.

    The O(n0.5) estimate for divisor count function d(n) is actually too conservative. I posted a time complexity analysis into a little bit more details to get a tighter bound. The overall complexity for this method is actually little o(n1+e) for any small e > 0.


Log in to reply
 

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