Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:
Input: “abab”
Output: True
Explanation: It’s the substring “ab” twice.
Example 2:
Input: “aba”
Output: False
Example 3:
Input: “abcabcabcabc”
Output: True
Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)
I thought about this problem for a long time, and then I used a shortcut:
- double is now a string
- Remove the head and tail (because if there is a substring, the first one is definitely the head of the substring, and the last one is definitely the tail).
- Then check if the double string contains the old string (if the old string is repeated, there are at least 2 substrings, and the new one has at least 4. After removing the beginning and end, there are exactly 2 left (if there were 3 original substrings, there would be 4 new ones), so it definitely contains it).
public class Solution { public booleanrepeatedSubstringPattern(Strings) { if (s . length() <= 1) return false; Strings2 = s + s; s2 = s2 . substring(1, s2 . length() - 1); if (!s2 . contains(s)) return false; return true; } } This websiteOriginal articleAll follow "Attribution-NonCommercial-ShareAlike 4.0 License (CC BY-NC-SA 4.0)Please retain the following annotations when sharing or adapting:
Original author:Jake Tao,source:「LeetCode – 459. Repeated Substring Pattern」
