LeetCode 459. Repeated Substring Pattern

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

This is the first string related question. Lots of the String algorithm questions look innocent, but when you dig into some of these questions, it takes some genius to come up with really smart and efficient algorithm. I remember learning KMP (knuth morris pratt) algorithm in class, and it really takes me a while to first understand what the algorithm is doing and then convince myself that it works. This problem is not as hard or as complicated as the KMP algorithm. The second solution is indeed quite smart.

My initial idea is that when you keep on rotating a valid repeated substring, you will eventually get back the same string. s[i:] + s[:i] is a pythonic way to rotate a string. It is easier to understand what rotating a string means. Let's say we have "abc", we shift the string to the left by one, we will have "bca" where "a" got pushed around to the end. Shift one more time, we have "cab".

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        ans = False
        if n == 1:
            ans = False
        else:
            for i in range(1, n):
                if s[i] == s[0]:
                    ans = (s[i:] + s[:i]) == s
                    if ans:
                        break
        return ans

Here comes the smart algorithm:

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """

        return s in s[1:] + s[:-1]

Why does it work? Consider the case for a valid repeated substring. Suppose the string has a repeating pattern "abc", and it repeated twice. The string is "abcabc" then when we form the string by concatenating the substring that cut off the first character and the substring that cut off the last character. We form the string "bc[abcabc]ab", we see the original string is in there as bolded. By cutting one character off the pattern, we were taking away one repeating pattern away from the original string. However, when we concatenate the substring that takes the first character away with the substring with last charater cutoff, we will get the back the original string embedded in this new string.