arcbjorn

thoughtbook

Wednesday, December 28, 2022

Repeated substring pattern

Leetcode 459 problem.

A function, given a string s, to check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Go

  • Time complexity: O(nlogn)O(n * log_n) - n is a length of a string
  • Auxiliary space: O(1)O(1) - constant amount of space
import "strings"

func repeatedSubstringPattern(s string) bool {
    length := len(s)
    for i := length / 2; i >= 1; i-- {
        // length must always be dividable by the length of repeated string
        if length % i != 0 {
            continue
        }

        // create a string and compare with given
        if strings.Repeat(s[:i], length / i) == s {
            return true
        }
    };
    
    return false
}
Creative Commons Licence