這是悅樂書的第289次更新，第307篇原創
01 看題和準備
今天介紹的是LeetCode算法題中Easy級別的第156題（順位題號是686）。給定兩個字符串A和B，找到A必須重復的最小次數，使得B是它的子字符串。 如果沒有這樣的解決方案，返回-1。例如：
輸入：A =“abcd”，B =“cdabcdab”。
輸出：3
說明：因為重復A三次（“abcdabcdabcd”），B是它的子串; 和B不是A重復兩次的子串（“abcdabcd”）。
注意：A和B的長度在1到10000之間。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
特殊情況：如果B的長度為0，直接返回0。
正常情況：使用循環，依次累加A，然后判斷在累加后的字符串中是否存在字符串B，借助indexOf方法實現，同時統計累加的次數，如果能夠找到，就返回最后的次數。但是有一種情況需要考慮，如果B根本就不是由A多次累加組成，那么循環就容易變成死循環，所以，在循環外面我們取得A和B的長度之商，如果count比商要大2，就直接返回-1。
public int repeatedStringMatch(String A, String B) {if (B.length() == 0) {return 0;}int len = B.length()/A.length();int count = 1;String C = A;while (C.indexOf(B) < 0) {C += A;count++;if (count-len > 2) {return -1;}}return count;
}03 第二種解法
在第一種解法的基礎上，我們還可以再優化下。依舊使用循環，只要A的長度小于B的長度，就累加一次A，并記數，然后開始判斷累加后的A與B是否存在B是A的子串的關系。如果在A中能夠直接找到B，就返回count；如果需要再累加一次A才能找到B，那么就返回count加1；如果前面兩種情況都不符合，就返回-1。
public int repeatedStringMatch(String A, String B) {int count = 1;StringBuilder sb = new StringBuilder(A);while (sb.length() < B.length()) {sb.append(A);count++;}if (sb.indexOf(B) >= 0) {return count;}if (sb.append(A).indexOf(B) >= 0) {return count+1;}return -1;
}04 小結
算法專題目前已日更超過四個月，算法題文章157+篇，公眾號對話框回復【數據結構與算法】、【算法】、【數據結構】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支持！
)
