LeetCode演算法題-Repeated Substring Pattern（Java實現）
這是悅樂書的第236 次更新，第249 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第103題（順位題號是459）。給定非空字串檢查是否可以通過獲取它的子字串並將子字串的多個副本附加在一起來構造它。 您可以假設給定的字串僅由小寫英文字母組成，其長度不超過10000。例如：
輸入：“abab”
輸出：true
說明：它是子串“ab”兩次。
輸入：“aba”
輸出：false
輸入：“abcabcabcabc”
輸出：true
說明：它是子串“abc”四次。 （和子串“abcabc”兩次。）
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
特殊情況：當s為null或者s的長度小於等於1時，直接返回false。
正常情況：從1開始，擷取s的第0到第1位，然後使用StringBuilder類，累加擷取的字串組成新的字串，然後比較新舊字串是否相等，如果相等，直接返回true，反之，擷取s的第0到第2位，繼續之前的操作和判斷。
在外層迴圈中，指標i是小於等於二分之s的長度的，因為子字串至少要匹配一次，所以i是小於等於len/2的。在外層迴圈開始的時候，我們可以加多一步判斷，省去沒必要的計算，如果len對i取餘不等於0，就結束當前迴圈，進入下一次迴圈。例如，len等於9，i則小於等於4，我們只用計算i等於1和3的情況即可，2和4是不可能滿足子字串要求的。
public boolean repeatedSubstringPattern(String s) {
if (s == null || s.length() <= 1) {
return false;
}
int len = s.length();
for (int i=1; i<=len/2; i++) {
if (len%i != 0) {
continue;
}
String str = s.substring(0, i);
StringBuilder sb = new StringBuilder();
for (int j=0; j<len/i; j++) {
sb.append(str);
}
if (s.equals(sb.toString())) {
return true;
}
}
return false;
}
03 第二種解法
特殊情況：當s為null或者s的長度小於等於1時，直接返回false。
正常情況：思路和第一種解法類似，只是將內層迴圈中使用StringBuilder類換成了擷取字串，每次從i開始，往後擷取i個長度的子串，然後判斷兩個子串是否相等。
public boolean repeatedSubstringPattern2(String s) {
if (s == null || s.length() <= 1) {
return false;
}
int len = s.length();
for (int i=1; i<=len/2; i++) {
if (len%i != 0) {
continue;
}
String str = s.substring(0, i);
boolean flag = true;
for (int j=i; j<len; j += i) {
if (!str.equals(s.substring(j, j+i))) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
04 第三種解法
此解法來自提交程式碼裡排第一位置的，思路比較巧妙，利用了kmp演算法，感興趣的同學可以去看下CSDN上July大神的一篇介紹kmp演算法的博文，傳送門：https://blog.csdn.net/v_JULY_v/article/details/7041827
public boolean repeatedSubstringPattern3(String s) {
int len = s.length();
if (len < 2) {
return false;
}
char lastChar = s.charAt(len-1);
int index = s.indexOf(lastChar);
// 思想是： 找到最後一個字元所在的位置，那麼如果是pattern，則一定有
// len％（index＋1）＝＝ 0。 那麼pattern應該是從0到index位置的子串。
while (index >=0 && index < len-1) {
if (len % (index+1) == 0) {
String pattern = s.substring(0, index+1);
if (foundPattern(s, pattern)) {
return true;
} else {
//否則找下一個出現lastChar的位置
index = s.indexOf(lastChar, index+1);
}
} else {
//否則找下一個出現lastChar的位置
index = s.indexOf(lastChar, index+1);
}
}
return false;
}
private boolean foundPattern(String s, String pattern) {
int fromIndex = pattern.length();
int n = fromIndex;
while (fromIndex < s.length()) {
if (!pattern.equals(s.substring(fromIndex, fromIndex + n))) {
return false;
}
fromIndex += fromIndex;
}
return true;
}
05 第四種解法
還有更加瘋狂的解法，兩行程式碼搞定。方法是將s和自身連線組成一個新的字串，然後從第二位開始，擷取子字串到倒數第二位，得到的子字串再去判斷是否包含s字串序列。
思路是這樣的，如果s是由可連續的子串組成，那麼將其重複一遍後，重複子串的數量是原來的2倍，再將其去頭去尾，那麼中間至少會存在一個完整的s，如果s是由單字母組成，就會存在多個s。反之，如果s不是由連續子串組成，在進行上面的操作後，中間部分是不可能存在s的，因為不具備連續性，再重複一遍的新字串肯定也不具備連續性。
此解法的時間複雜度不是O(1)，因為使用了contains方法，時間複雜度好的情況是O(n)，壞的情況是O(n^2)。
public boolean repeatedSubstringPattern4(String s) {
String str = s + s;
return str.substring(1, str.length() - 1).contains(s);
}
06 小結
演算法專題目前已日更超過三個月，演算法題文章103+篇，公眾號對話方塊回覆【資料結構與演算法】、【演算法】、【資料結構】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！