String - 28. Implement strStr()

28. Implement strStr()

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

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

思路：

返回子串在字符串中起始的索引，一般字符串匹配就是暴力匹配或者kmp，这里就直接匹配来做。

代码：

java：

class Solution {

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        /*// 1. substring:
        for (int i = 0; i <= haystack.length() - needle.length(); i++)
            if (haystack.substring(i, i+needle.length()).equals(needle)) return i;
        return -1;
        */
        
        /*// 2. java api:
        return haystack.indexOf(needle);
        */

        // 3. java indexOf api source code:
        char first = needle.charAt(0);
        int max = (haystack.length() - needle.length());
        for (int i = 0; i <= max; i++) {
            // Look for first character.
            if (haystack.charAt(i) != first) {
                while (++i <= max && haystack.charAt(i) != first);
            }
            // Found first character, now look at the rest of value
            if (i <= max) {
                int j = i + 1;
                int end = j +  needle.length() - 1;
                for (int k = 1; j < end && haystack.charAt(j) == needle.charAt(k); j++, k++);
                if (j == end) {
                    // Found whole string.
                    return i;
                }
            }
        }
        return -1;
    }
}