28.实现strStr()

1.题目

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例：

输入: haystack = "hello", needle = "ll"
输出: 2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

2.思路

一行代码搞定：

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle == null){
            return -1;
        }else{
             return haystack.indexOf(needle);   
        }
    }
}

当然，我们这里要看一下，indexOf这个方法的源码是如何实现的：
贴源码：

static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }

        char first = target[targetOffset];
        //找到遍历的最大位置
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            //首先寻找第一个相等字符的位置，不相等则一直向后找，直到找到为止
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            //此处再次判断，如果大于了边界，可以直接返回-1
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                //这个循环找到和目标字符串完全相等的长度
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);
                //如果完全相等的长度和目标字符串长度相等，那么就认为找到了
                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

总结：这个方法首先会查找子字符串的头字符在此字符串中第一次出现的位置，再以此位置的下一个位置开始，然后将子字符串的字符依次和此字符串中字符进行比较，如果全部相等，则返回这个头字符在此字符串中的位置；如果有不相等的，则继续在剩下的字符串中查找，继续进行上面的过程，直到查找到子字符串或没有找到返回-1为止。