要成功就做一百题-89

题目名称

实现字符串函数strStr() ，第28题

描述

//实现 strStr() 函数。 
//
// 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如
//果不存在，则返回 -1。 
//
// 示例 1: 
//
// 输入: haystack = "hello", needle = "ll"
//输出: 2
// 
//
// 示例 2: 
//
// 输入: haystack = "aaaaa", needle = "bba"
//输出: -1
// 
//
// 说明: 
//
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 

解题思路

目的是找出某个字符串在另一个字符串的起始位置。首先是两种特殊情况，如果没有找到返回-1，如果输入的匹配字符串为空，则返回0，算作约定。

其次处理一般情况，这里把要匹配的字符串称作原始字符串，待匹配的称为模式字符串。定义两个标记位i,j，初始都为0。然后比较字符的大小，截止条件是到达两个字符串最大长度。
进行比较，如果相等，继续往后面匹配；
如果不相等，这里是重点，j标记模式字符串所以重置，重新开始，让值等于0；
而对于原始字符串，之前匹配过的就不再匹配了，但是当前匹配的j长度，要掉头回去，这里他新的进度就是当前i-j的值，然后从下一个位置开始即i-j+1。
到最终全部匹配，到达截止条件后，判断模式匹配的值j是否是模式的长度，如果是，就返回i-j，掉头回去，代表匹配到的位置，如果不是就说明没有匹配到，返回-1，如下就是全部代码。

代码

    public int strStr(String haystack, String needle) {
        if (null == needle || "".equals(needle)) {
            return 0;
        }

        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }

        return j == needle.length() ? i - j : -1;
    }

    @Test
    public void test28() {
        //"mississippi" "issip"
        String haystack = "mississippi";
        String needle = "issi";
        System.out.println(strStr(haystack, needle));
    }

总结

这个思路看起来简单，但是细节上要把握很多，还是要多消化下的。