Easy！

題目描述：

實現?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()?定義相符。

解題思路：

這道題讓我們在一個字符串中找另一個字符串第一次出現的位置，那我們首先要做一些判斷，如果子字符串為空，則返回0，如果子字符串長度大于母字符串長度，則返回-1。

然后我們開始遍歷母字符串，我們并不需要遍歷整個母字符串，而是遍歷到剩下的長度和子字符串相等的位置即可，這樣可以提高運算效率。然后對于每一個字符，我們都遍歷一遍子字符串，一個一個字符的對應比較，如果對應位置有不等的，則跳出循環(huán)，如果一直都沒有跳出循環(huán)，則說明子字符串出現了，則返回起始位置即可。

C++解法：

1 class Solution { 2 public: 3 int strStr(string haystack, string needle) { 4 if (needle.empty()) return 0; 5 int m = haystack.size(), n = needle.size(); 6 if (m < n) return -1; 7 for (int i = 0; i <= m - n; ++i) { 8 int j = 0; 9 for (j = 0; j < n; ++j) { 10 if (haystack[i + j] != needle[j]) break; 11 } 12 if (j == n) return i; 13 } 14 return -1; 15 } 16 };

?

轉載于:https://www.cnblogs.com/ariel-dreamland/p/9134059.html

總結

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

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