文章目錄
- 題目
- 暴力解法
- 代碼
- 附圖
- KMP 演算法，可參考[請收好這一封 KMP 演算法 的信 - Java 和 c 實作](https://blog.csdn.net/DarkAndGrey/article/details/121928624?spm=1001.2014.3001.5501)這篇文章
題目
?
暴力解法
運用 StringBuilder 和 indexOf 來解決問題
StringBuilder 用來 存盤存盤 字串 a 的疊加結果，
indexOf 用來 檢查 字串 a 重疊后 的 結果里 是否包含 子串 b，
?
代碼
class Solution {
public int repeatedStringMatch(String a, String b) {
StringBuilder sb = new StringBuilder();
int result = 0; // 記錄 重復疊加
// 重復疊加， 如果 主串 還沒有 子串長，那么，主串a 是不可能包含子串 b de
while(sb.length() < b.length() && ++result>0 ){
sb.append(a);
}
sb.append(a);// 主串 “a” 跟 子串b，在經過上面的疊加，主串長度 >= 子串長度
// 但是 并不意味著：此時的主串就包含子串，所以 我們自行疊加了一次，
// 獲取 子串b 在主串中的 初始位置下標 / 子串 b 的第一個字符， 在主串中出現位置的下標
int index = sb.indexOf(b);
if(index == -1){ // 要知道下標是不可能為負的，所以，-1 代表 主串中不包含子串
return -1;// 按照題目的要求： 回傳 -1.
}
return index + b.length() > a.length()* result ? result+1 : result;
// 在回傳的時候：你會發現我們 讓 index 和 子串長度相加，再去判斷 和 主串 誰長，
// 至于為什么 子串長度 要加上 index，你可以這么想： index 的位置 是 子串在主串中 第一次出現的位置下標
// 那么，就是說： 如果主串包含子串， 主串 至少比 子串 長 index，
// 但是！ 想想看 如果我們子串長度 加上了這個長度，按道理 主串 和 子串 之間，只存在 長度相等，或 子串比主串短，
// 結果卻是 大于！就是說 我們疊加次數少了！
// 但是！為何 主串能找到 子串，照理說應該是找不到的，
// 注意到我們前面 while 回圈 后面，我們手動 疊加的那一下嗎？
// 就是為了防止 出現 這種情況，
// 所以回傳值 result + 1 ： 意味著疊加次數加一
}
}
附圖
?
KMP 演算法，可參考請收好這一封 KMP 演算法 的信 - Java 和 c 實作這篇文章
class Solution {
public int repeatedStringMatch(String a, String b) {
StringBuilder sb = new StringBuilder();
int result = 0;
while(sb.length() < b.length() && ++result > 0){
sb.append(a);
}
sb.append(a);
int index = KMP(sb.toString(),b,0);
if(index == -1){
return -1;
}
return index + b.length() > a.length()*result ? result+1 : result;
}
public static int KMP(String str,String sub,int pos){
if(str == null || sub == null){
return -1;
}
if(str.length() == 0 || sub.length() == 0){
return -1;
}
int strLen = str.length();
int subLen = sub.length();
if(pos<0 || pos >= strLen){
return -1;
}
int i = pos;
int j = 0;
int[] next = new int[subLen];
getNext(sub,next);
while( i < strLen && j < subLen){
if(j == -1 || str.charAt(i) == sub.charAt(j)){
i++;
j++;
}else{
j = next[j];
}
}
if(j >= subLen){
return i-j;
}
return -1;
}
public static void getNext(String sub, int[] next){
next[0] = -1;
// next[1] = 0;看完過推薦文章，這里是要省略的，因為 子串可能只有一個字符，如果加上這句代碼就會發生越界例外
int k = -1;
int j = 1;
while( j < sub.length()){
if(k == -1 || sub.charAt(j-1) == sub.charAt(k)){
next[j] = k+1;
k++;
j++;
}else{
k = next[k];
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/390645.html
標籤：java
上一篇：Jaeger知識點補充