Leetcode: Repeated substring pattern20 Sep 2022 by Friedrich Ewald · 2 min read
The task is to find out if a given string is comprised of multiple identical substrings. The first observation is that the substring cannot be longer than half of the length of the original string. The second observation is that the length of the total string has to be a multiple of the string that is tested, if it is not it can be discarded right away. Lastly, a string with the length of one can be discarded immediately.
The main idea is to try out every string from size
break immediately of the next character is not the expected one. As an additional optimization, substrings whose length do not fit into the whole string can be discarded immediately.
Runtime: 245 ms, faster than 34.66% of Python3 online submissions for Repeated Substring Pattern. Memory Usage: 14 MB, less than 59.35% of Python3 online submissions for Repeated Substring Pattern.