LeetCode0459. 重複的子字元串

一. 題目

1. 題目

   給定一個非空的字元串，判斷它是否可以由它的一個子串重複多次構成。給定的字元串隻含有小寫英文字母，并且長度不超過10000。

2. 示例

   

二. 方法一: 暴力法(逾時)

1. 解題思路
2. 解題代碼

   def repeatedSubstringPattern(self, s: str) -> bool:
       size = len(s)
       # 從 二等分開始增加等分次數
       for m in range(2, size + 1):
       	# 擷取每給等分的起始下标
           for i in range(0, size, int(size / m)):
           	# 如果不是每個等分都相等, 則說明不是
               if s[i: int(size / m) + i] != s[0: int(size / m)]:
                   break
           else:
               return True
       return False
              

3. 分析

三. 方法二

1. 解題思路
   1. 将字元串依次截取成整份
   2. 然後再将第一份拼成和原字元串等長的字元串
   3. 比較兩個字元串是否相等, 如果相等則傳回True
   4. 如果不相等則增加截取的份數
   5. 如果截取成n份仍不相等, 就傳回False
2. 解題代碼

   def repeatedSubstringPattern(self, s: str) -> bool:
       size = len(s)
       for m in range(1, size):
       	# size % m == 0 用于截枝
           if size % m == 0 and s[0: m] * int(size / m) == s:
           	return True
       return False
              

3. 分析

   時間複雜度: O(n^2)

   空間複雜度: O(1)

四. 方法三: 雙倍字元串

1. 解題思路

   題解: 圖解一下雙倍字元串的解法

   1. 将字元串生成為2倍字元串
   2. 如果字元串不包含重複的子字元串, 則在2倍字元串去掉頭尾字元串後, 不可能再包含原始字元串
   3. 如果字元串包含重複的子字元串, 則再2倍字元串去掉頭尾字元後, 仍然包含原始字元串
   4. 是以可以根據是否包含原始字元串來判斷包含重複的子字元串
2. 解題代碼

   def repeatedSubstringPattern(self, s: str) -> bool:
   	# 去掉其實原始和最後一個元素的原因是, 避免和源字元串比對成功
       res = (s * 2)[1: -1]
       if s in res:
           return True
       else:
           return False
              

3. 分析

   時間複雜度: O(n)

   空間複雜度: O(n)