题目如下:
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input:haystack = "hello", needle = "ll"Output:2
Example 2:
Input:haystack = "aaaaa", needle = "bba"Output:-1
分析:
题目很简单,就是查找有没有字串,有的话就返回字串在字符串中的首字母下标
我觉得这个测试用例简直深坑,比如haystack = "", needle = "",output竟然是0,如果haystack = "a", needle = "",output也为零,唉不知道这样做的意义何在啊~一开始提交的时候就是被这两坑了啊!!!
其次我发现了自己的思维漏洞,一个测试用例为Input:haystack = “mississippi", needle = "issip”,Output: 4.
一开始我的思路得到的答案是-1,即不存在,因为我对于haystack的计数器 i 是一直递增的,这个测试用例告诉,遇到一开始重合,后面字符不重合时,我们是需要回退的,如下图:
那么回退的公式就是 i = i - j + 1,即找到首字母相同的下一位,j 归位 0,继续compare。
代码如下: