描述#
實現 strStr() 函數。
給定一個 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() 定義相符。
思路#
- needle 空串時返回 0
- 遍歷 haystack 字串，判定當前字元與 needle 字元是否相同，不同則繼續遍歷
- 若與 needle 字元相同，則匹配剩餘字元是否相同，needle 遍歷結束，返回匹配位置，haystack 遍歷結束，返回 - 1，發現不匹配字元，跳出來繼續匹配首字元
- haystack 遍歷完成仍未匹配完成，返回 - 1
int strStr(char * haystack, char * needle) {
if(strlen(needle) == 0)
return 0;
for(int i=0;haystack[i] != '\0';i++) {//遍歷字串
if(needle[0] == haystack[i]) {//查找首字元匹配
for(int j=0;;j++) {//剩餘字元匹配
if(needle[j] == '\0')
return i;
if(haystack[i+j] == '\0')
return -1;
if(needle[j] != haystack[i+j]) //剩餘字元不匹配
break;//跳出當前匹配
}
continue;//查找下一首字元
}
}
return -1;//首字元未匹配成功
}
注意#
- 匹配時的返回條件檢測順序有嚴格要求，needle 匹配完成返回成功，needle 匹配未完成而 haystack 遍歷完成返回 - 1，最後才是判定是否匹配