Question:

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

Thinking:

  • Method1: Iterate and compare 
      class Solution {
      public int strStr(String haystack, String needle) {
          int len = needle.length();
          int slen = haystack.length();
          if(len == 0) return 0;
          int i = 0;
          while(i + len <= slen){
              if(haystack.substring(i, i + len).equals(needle)){
                  return i;
              }else{
                  i++;
              }
          }
          return -1;
      }
  }

二刷

二刷的时候已经研究了KMP算法，直接上KMP算法。 KMP算法讲解

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0) return 0;
        return kmp(haystack, needle);
    }
    private int[] getNext(String pattern){
		char[] arr = pattern.toCharArray();
		int len = pattern.length();
		int[] next = new int[len];
		next[0] = -1;
		for(int i = 1, j = -1; i < len; i++){
			while(j > -1 && arr[j + 1] != arr[i]){
				j = next[j];
			}
			if(arr[i] == arr[j + 1]) j++;
			next[i] = j;
		}
		return next;
	}
	public int kmp(String text, String pattern){
		int[] next = getNext(pattern);
		char[] tArr = text.toCharArray();
		char[] pArr = pattern.toCharArray();
		int tLen = text.length();
		int pLen = pattern.length();
		int j = -1;
		for(int i = 0; i < tLen; i++){
			while(j > -1 && tArr[i] != pArr[j + 1]){
				j = next[j];
			}
			if(tArr[i] == pArr[j + 1]) j++;
			if(j == pLen - 1) return i - pLen + 1;
		}
		return -1;
	}
}