LeetCode - Repeated Substring Pattern

LeetCode で「難易度: Easy」とされている Repeated Substring Pattern を解いた。与えられた文字列が「部分文字列を繰り返している文字列かどうか」を判定せよという問題だ。たとえば "abab" は "ab" を繰り返しているので true であり、"aba" は部分文字列を繰り返してできる文字列ではないので false である。

文字列の長さが 10^4 なので、部分文字列を繰り返しているのであれば、最長でも 10^4/2 の範囲を調べればよい。このくらいであれば確かにブルートフォースできそうなので、難易度は Easy でもよいかもしれない。

しかし、解答の Approach #2 Concatenation はずっと簡潔である。

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

僕はこれを理解するのに時間がかかった。未来の自分のために、これが何をしているのか書いてみよう。

(s + s)[1: -1] は与えられた文字列を二度繰り返して、そこから先頭と末尾の1文字を削ったものだ。つまり、"ab" が与えられたのであれば "abab" から先頭と末尾を削って "bab" である。これには "ab" が含まれているので true が返る。"aba が与えられたのであれば、(s + s)[1: -1] は "baab" であり、これは与えられた文字列を含まない。

なぜこれでうまく行くのか。与えられる文字列 s が部分文字列を繰り返したものであれば、s + s は最小でも部分文字列を 4 つ含むことになる。前後の1文字を削ることで、少なくとも 2 つの繰り返される部分文字列を持つことになる。それこそが与えられる文字列 s となる。