文章目錄

• • • 題目描述
    • 我的解法
    • 反思
    • 優化
    • 其他思路
    • 總結
    • Github

題目描述

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。

示例 1:

輸入: haystack = “hello”, needle = “ll”
輸出: 2

示例 2:

輸入: haystack = “aaaaa”, needle = “bba”
輸出: -1

說明:

當 needle 是空字符串時，我們應當返回什么值呢？這是一個在面試中很好的問題。

對于本題而言，當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

---

我的解法

public int strStr(String haystack, String needle) {//特殊情況if(null == needle || "".equals(needle))return 0;if(null == haystack || "".equals(haystack)||!haystack.contains(needle))return -1;//接下來肯定是haystack包含needle的情況char needleFirstChar = needle.charAt(0);//獲取needle的第一位字符int returnInt = haystack.indexOf(needleFirstChar);//找到needle第一位字符在haystack中第一次出現的位置，初始化String partHaystack = haystack.substring(returnInt,returnInt+needle.length());//partHaystack是從returnInt開始截取needle長度的字符串while(!needle.equals(partHaystack)){//先判斷partHaystack是否跟指定字符串相等returnInt++;returnInt += haystack.substring(returnInt).indexOf(needleFirstChar);//取從returnInt之后以為到末尾組成的新字符串中，第一次出現needleFirstChar的位置partHaystack = haystack.substring(returnInt,returnInt+needle.length());//從該位置截取needle長度的字符串用于作比較}return returnInt;}

用間：5ms
戰勝：90.31%

---

反思

其實String類的contains方法就提供了一個參數為String的類似的方法。不過參數不能為空，否則會報空指針異常“NullPointerException”

/*** Returns the index within this string of the first occurrence of the* specified substring.** <p>The returned index is the smallest value <i>k</i> for which:* <blockquote><pre>* this.startsWith(str, <i>k</i>)* </pre></blockquote>* If no such value of <i>k</i> exists, then {@code -1} is returned.** @param str the substring to search for.* @return the index of the first occurrence of the specified substring,* or {@code -1} if there is no such occurrence.*/public int indexOf(String str) {return indexOf(str, 0);}/*** Returns the index within this string of the first occurrence of the* specified substring, starting at the specified index.** <p>The returned index is the smallest value <i>k</i> for which:* <blockquote><pre>* <i>k</i> &gt;= fromIndex {@code &&} this.startsWith(str, <i>k</i>)* </pre></blockquote>* If no such value of <i>k</i> exists, then {@code -1} is returned.** @param str the substring to search for.* @param fromIndex the index from which to start the search.* @return the index of the first occurrence of the specified substring,* starting at the specified index,* or {@code -1} if there is no such occurrence.*/public int indexOf(String str, int fromIndex) {return indexOf(value, 0, value.length,str.value, 0, str.value.length, fromIndex);} /*** Code shared by String and StringBuffer to do searches. The* source is the character array being searched, and the target* is the string being searched for.** @param source the characters being searched.* @param sourceOffset offset of the source string.* @param sourceCount count of the source string.* @param target the characters being searched for.* @param targetOffset offset of the target string.* @param targetCount count of the target string.* @param fromIndex the index to begin searching from.*/static int indexOf(char[] source, int sourceOffset, int sourceCount,char[] target, int targetOffset, int targetCount,int fromIndex) {if (fromIndex >= sourceCount) {return (targetCount == 0 ? sourceCount : -1);}if (fromIndex < 0) {fromIndex = 0;}if (targetCount == 0) {return fromIndex;}char first = target[targetOffset];int max = sourceOffset + (sourceCount - targetCount);for (int i = sourceOffset + fromIndex; i <= max; i++) {/* Look for first character. */if (source[i] != first) {while (++i <= max && source[i] != first);}/* Found first character, now look at the rest of v2 */if (i <= max) {int j = i + 1;int end = j + targetCount - 1;for (int k = targetOffset + 1; j < end && source[j]== target[k]; j++, k++);if (j == end) {/* Found whole string. */return i - sourceOffset;}}}return -1;}

---

優化

public int strStr1(String haystack, String needle) {//特殊情況if(null == needle || "".equals(needle))return 0;elsereturn haystack.indexOf(needle);}

用時：6ms（可能電腦及網絡性能影響）
戰勝：80.45%

---

其他思路

我最先想到可以先找到needle首個字符在haystack的位置，在用for循環遍歷haystack這個字符串needle的長度位的字符，讓他們一一比較，如果不匹配則再找到下一個與needle首個字符一致的字符位置，接著遍歷。這樣可以省去重復建造字符串所導致的系統開銷，從而稍稍能縮短運行時間。但其實String類原生的實現方法跟這種方法差不多，具體可以參考一下人家寫的代碼。

---

總結

while循環是先判斷后循環 ，而do–while循環是先循環后判斷

關于substring的雙參方法substring(a, b),指的是截取字符串 [a,b)左閉右開 位字符

The substring begins at the specified {@code beginIndex} and
extends to the character at index {@code endIndex - 1}.
Thus the length of the substring is {@code endIndex-beginIndex}

還需多看jdk源碼

---

Github

LeetCode刷題筆記

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode-28 实现strStr()的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。