Repeated Substring Pattern (E)
題目
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.)
題意
判斷一個字串是否能有其中的一個子串重復多次得到，
思路
最簡單的直接暴力遍歷即可，
另一種比較好的方法是先用KMP演算法的前半部分計算next陣列，這樣可以得到字串s的最長公共前后綴，以字串 abababab 為例：
S被分為了前綴AB和后綴BC，如果AB的長度是C的整數倍，那么我們以C的長度為單位將S進行劃分得到上圖，因為AB和BC是相同的字串，顯然同一色塊的子串是相同的；同時因為B是公用部分，上下對應色塊位置的子串也是相同的，結合這兩點，我們就可以證明所有色塊的子串都是相同的，
代碼實作
Java
暴力法
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
for (int i = 1; i <= len / 2; i++) {
if (len % i == 0 && s.substring(0, i).repeat(len / i).equals(s)) {
return true;
}
}
return false;
}
}
KMP
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
int[] next = new int[len];
int i = 0, j = 1;
while (j < len) {
if (s.charAt(j) == s.charAt(i)) {
next[j++] = ++i;
} else if (i > 0) {
i = next[i - 1];
} else {
++j;
}
}
return next[len - 1] > 0 && next[len - 1] % (len - next[len - 1]) == 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143963.html
標籤：其他
下一篇：LeetCode-鏈表專題