Leetcode # 459. Repeated Substring Pattern

Problem

n := len(s)
Check 「∃ s’ = s[i:n], 0 < i < n s.t. s == s’ * k, k >= 2」

 https://leetcode.com/problems/repeated-substring-pattern/

First Solution

Time Complexity: O(len(s) ** 2)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def repeatedSubstringPattern(self, s: str) -> bool:
    for times in range(2, len(s) + 1):
      if len(s) % times != 0:
        continue
    
      # Check for times is a prime number.
      if times != 2 and times % 2 == 0:
        continue
      for t in range(3, int(times ** 0.5) + 1):
        if times % t == 0:
          continue
    
      is_RSP = True
      l = len(s) // times # you should use "//" then l is a integer
      for i in range(l):
        for j in range(1, times):
          if s[i] != s[j * l + i]:
            is_RSP = False
            break
        if not is_RSP:
          break
      if is_RSP:
        return True
    return False

Best Solution (lambda s: True if s in (s + s)[1:-1] else False)

• Time Complexity:
  • O(len(s) ** 2) (in Python & Java)
  • O(len(s)) in C
  • How to do s in (s + s)[1:-1] in O(len(s)), 
    reference Leetcode # 28. Find the Index of the First Occurrence in a String.
• Space Complexity: O(len(s))

(The input and output generally do not count towards the space complexity.)

class Solution:
  def repeatedSubstringPattern(self, s: str) -> bool:
    return True if s in (s + s)[1:-1] else False

Last Updated on 2023/08/21 by A1go