Implement strStr()

Question:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Difficulty: Easy

Link: https://leetcode.com/problems/implement-strstr/

Solution:

There are three solutions to this problem. (The code is the second solution)

First one is Brute Force. The time complexity is O(n^2). Use two pointers in two "for" loops, the outer loop is used for scanning all the letter in haystack. The outer pointer will point to a letter each time. And the inner pointer will scan the X times (X = length of needle) afterward to check if the pattern is our needle.

Second one is a O(n) solution, it uses two pointers in one loop. The while loop will check if the pointer of haystack is out of range. In the loop, we will check if the haystack pointer equals to the letter that pointed by needle pointer. If they are same for several times, and the needle pointer has pointed to the last position. It means we find the needle in haystack and then we will return the start position in haystack (s_count - n_count + 1). But if we're not that lucky and there are some similar patterns in haystack (haystack: mississipi, needle: issip). We need to move haystack pointer to the position we found same letter between haystack and needle. And move needle pointer to its beginning. Return -1 for the situation that we don't find needle in haystack. What's more, don't forget to process the corner cases. It will help you avoid some error and improve efficiency in solution.

Third one is K (I) M (Don't) P (Know).

Code:

public class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        if(haystack.length()==0){
            return -1;
        }
        if(haystack.length()<needle.length()){
            return -1;
        }

        int s_count = 0;    /*haystack pointer*/
        int n_count = 0;    /*needle pointer*/

        while( s_count < haystack.length() ){
            if(haystack.charAt(s_count) == needle.charAt(n_count)){
                n_count++;
                if(n_count == needle.length()){
                    return s_count-n_count+1;
                }
            }
            else{
                s_count = s_count - n_count;
                n_count=0;
            }

            s_count++;
        }

        return -1;
    }
}