题意
实现 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() 定义相符。
算法
如果haystack字符串为空,直接返回0;
若needle长度大于haystack,返回-1;
遍历给定haystack字符串,如果存在元素与needle字符串的首字符相同,继续;否则,返回 -1;
比较后续字符串,若都相同,返回当前索引值。(可以使用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 };