Problem:

Implement strStr().

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

Knowledge Preparation:

1. strStr function. (Search String for Substring)  the strStr function searches within the string pointed to by s1 for the string pointed to by s2. It returns a pointer to the first occurrence in s1 of s2.

2.To make it easier, this problem is asking us to search the String ‘needle’ in the String ‘haystack’, and return the first occurrence of needle.

3. About corner case: strStr(Any String.””)  return 0;

Method 1: Brute Force

Use two pointers. If every character matches, then return the index, or continue to compare.

Several details:

1. Check the remaining length before comparison. It could significantly reduce the time.

2. First check if exceeding the length, then get the character. If the sequence is reversed, running time error (Out of boundary exception) may occur.

3. Do not forget corner case. strStr(Any String.””)  return 0;

Code for method 1:

public class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0 && haystack.length() == 0) return 0;
        if (needle == null  && haystack == null) return 0;
        if (needle == null || needle.length() == 0) return 0;

        if (haystack == null || haystack.length() == 0) return -1;

        int idx0 = 0; // record the starting index in haystack
        int idx1 = 0; // move through the haystack
        int idx2 = 0; // move throught the needle

        while (idx0 <= haystack.length()-needle.length()){
            // judging the length is very important! Or it won't pass
            idx1 = idx0;
            idx2 = 0;
            while (idx2 < needle.length() && idx1 < haystack.length() &&haystack.charAt(idx1) == needle.charAt(idx2)  ){
                idx1++;
                idx2++;
            }

            if (idx2 == needle.length()){
               return idx0;
            }else{
                idx0 ++;
            }
        }
        return -1;
    }
}

Another code for method 1:

The above code is not clear. To avoid dealing with edge cases separately, we could do the following:

public class Solution {
    public int strStr(String haystack, String needle) {
        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(j+i)) break;
            }
        }
    }
}

Method 2: KMP method

KMP method is known to solve the problem of checking if one string is a substring of another one.

// This is the KMP solution
public class Solution {
    public int strStr(String haystack, String needle) {

        int i = 0;
        int hlength = haystack.length();
        int nlength = needle.length();

        if (nlength == 0) {
            return 0;
        } else {
            //get the prefix values for string: needle.
            int[] form = KMPform(needle);

            while (i <= hlength - nlength) {
                int j = 0;
                while (j < nlength) {
                    if (haystack.charAt(i + j) != needle.charAt(j)) {
                        if (j == 0) {
                            i++;
                        } else {
                            i = i + j - form[j - 1] - 1;
                        }
                        break;
                    } else if (j == nlength - 1) {
                        return i;
                    }
                    j++;
                }
            }

            return -1;
        }
    }

    public int[] KMPform(String str) {
        int[] form = new int[str.length()];
        form[0] = -1;
        for (int i = 1; i < form.length; i++) {
            int index = form[i - 1];
            while (index >= 0 && str.charAt(i) != str.charAt(index + 1))
            {
                index = form[index];
            }
            if (str.charAt(i) == str.charAt(index + 1))
            {
                form[i] = index + 1;
            }
            else
            {
                form[i] = -1;
            }
        }
        return form;
    }

}