459 Repeated Substring Pattern 重復(fù)的子字符串
Description:
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:
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.)
題目描述:
給定一個(gè)非空的字符串雀监，判斷它是否可以由它的一個(gè)子串重復(fù)多次構(gòu)成双吆。給定的字符串只含有小寫英文字母，并且長度不超過10000会前。
示例:
示例 1:
輸入: "abab"
輸出: True
解釋: 可由子字符串 "ab" 重復(fù)兩次構(gòu)成好乐。
示例 2:
輸入: "aba"
輸出: False
示例 3:
輸入: "abcabcabcabc"
輸出: True
解釋: 可由子字符串 "abc" 重復(fù)四次構(gòu)成。 (或者子字符串 "abcabc" 重復(fù)兩次構(gòu)成瓦宜。)
思路:
- 類似找素?cái)?shù)的思路, 從 1個(gè)字符開始匹配到 1/2個(gè)長度的字符
時(shí)間復(fù)雜度O(n ^ 2), 空間復(fù)雜度O(n) - 正則表達(dá)式, 將要匹配的子字符串當(dāng)作一個(gè)組, 匹配到結(jié)尾, 這個(gè)組需要出現(xiàn)次數(shù)大于 1
時(shí)間復(fù)雜度O(n ^ 2), 空間復(fù)雜度O(n) - 考慮到 s是重復(fù)串, s + s也是重復(fù)串, 破壞 s + s的頭尾兩個(gè)字符, 剩下的如果包含 s, 則說明 s中有重復(fù)的子字符串
e.g.
- s = "aba" s + s = "abaaba" -> "baab" -> false
- s = "abab" s + s = "abababab" -> "babababa" -> true
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
代碼:
C++:
class Solution
{
public:
bool repeatedSubstringPattern(string s)
{
return (s + s).substr(1, s.size() * 2 - 2).find(s) != -1;
}
};
Java:
class Solution {
public boolean repeatedSubstringPattern(String s) {
return (s + s).substring(1, s.length() * 2 - 1).indexOf(s) != -1;
}
}
Python:
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return re.match(r"([a-z]+)\1+$", s) != None
