题意

实现 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() 定义相符

算法

  1. 如果haystack字符串为空,直接返回0;

  2. 若needle长度大于haystack,返回-1;

  3. 遍历给定haystack字符串,如果存在元素与needle字符串的首字符相同,继续;否则,返回 -1;

  4. 比较后续字符串,若都相同,返回当前索引值。(可以使用string.substr(index1, len))来实现

code

 1 class Solution {  2 public:  3     int strStr(string haystack, string needle) {  4         if(needle == "")  5             return 0;  6         int ans = -1;  7         int i, j;  8         bool flag;  9         for(i=0; i<haystack.length(); i++) 10  { 11             if(haystack[i] == needle[0]) 12  { 13                 flag = true; 14                 for(j=1; j<needle.length(); j++) 15  { 16                     if(haystack[i+j] != needle[j]) 17  { 18                         flag = false; 19                         break; 20  } 21  } 22                 if(flag == true) 23  { 24                     ans = i; 25                     break; 26  } 27  } 28  } 29         
30         return ans; 31  } 32 };

 后来更新的👇

1. 直接使用find()函数,只是让大家看看,也可以自己去看find函数的实现,别用它去刷题。

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

2. 部分使用substr()函数

 1 class Solution {
 2 public:
 3         int strStr(string haystack, string needle) {
 4         int len = haystack.length();
 5         int len1 = needle.length();
 6         if(len < len1)
 7             return -1;
 8         if(len1 == 0)
 9             return 0;
10         for(int i=0; i<len; i++)
11         {
12             if(haystack[i] == needle[0])
13             {
14                 if(haystack.substr(i, len1) == needle)//i-index; len-长度
15                     return i;
16             }
17         }
18         return -1;
19     }
20 };