博客

28. Implement strStr()

题目

实现strStr()。查找子字符串，如果找到，返回第一次出现的索引，如果不是子字符串返回-1。

例 1:

输入： haystack = “hello”, needle = “ll”

输出： 2

例 2:

输入： haystack = “aaaaa”, needle = “bba”

输出： -1

说明：如果needle是空的话，返回0；

代码块

方案一：java里面自带一个类

return(haystack.indexOf(needle));

方案二：暴力解

class Solution {
    public int strStr(String haystack, String needle) {
        int N = haystack.length();
        int M = needle.length();

        for(int i = 0; i <= N-M; i++){
            int j;
            for(j = 0; j < M; j++){
                if(needle.charAt(j) != haystack.charAt(i+j))
                    break;
            }
            if(j == M){
                return i;
            }
        }
        return -1;


     // for(int i = 0 ; ; i++){
          // for(int j = 0;  ; j++){
          // if(j == needle.length())
          // return i;
          // if(i + j == haystack.length())
          // return -1;
          // if(needle.charAt(j) != haystack.charAt(i+j))
          // break;
          // }
          // }
    }
}

代码分析

第一，就是引用java中自带的方法。

第二，暴力解答，两层循环，但是也是参考着写出来的。

1. （被注释掉的） 双层循环 ，i , j 分别跟踪两个字符串，如果j达到模型needle的长度，就返回索引；如果两者之和大于总长度，直接返回-1；如果不相等，则跳出循环（break是结束整个循环）。

2. （看的算法书）也是双层循环，总体差别并不大。控制了i的循环条件是N-M的差值。感觉就是修改了格式。

第三，使用KMP算法，我还没看。。懂。