LeetCode刷题【28】实现 strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：

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

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

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

Sunday算法实现

举个栗子说明，haystack字符串

h, e, l, l, o, s, h, e, l, l, d, o, h, e, l, d, l, o, h, e, l, w, l, o, q, h, e, l, l, o, w, h, e, l, l, o
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

needle字符串

l, o, h, e, l, w, l
0  1  2  3  4  5  6

1. 从头开始匹配，匹配失败，
2. 找到haystack第7个字符下标6位置的字符h，h字符在needle字符串l, o, h, e, l, w, l最后出现的下标为2，则从下标6位置的字符h往前找2位开始匹配，
3. 此时新开始匹配的下标为4，字符为o，依旧匹配失败，继续往后找needle字符串长度的位置在下标11位置发现字符o，此时o在needle中最后出现的位置为下标1，则往前找一位，从haystack的10下标开始匹配
4. 10下标的d不能和needle匹配，继续往后找needle长度个位置，依旧是字符o，在needle中最后出现的位置为下标1，则往前找一位从haystack的第16下标开始匹配，
5. 能完全匹配，结束，返回当前开始的下标16。

代码

class Solution {
    //Sunday算法实现
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        int[] lastPos = new int[256];
        for (int i = 0; i < needle.length(); i++) {
            lastPos[needle.charAt(i)] = i;
        }
        for (int i = 0; i + m <= n; i += (m - lastPos[haystack.charAt(i+m)])) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i+j) == needle.charAt(j)){
                    continue;
                }
                flag = false;
                break;
            }
            if (flag){
                return i;
            }
            if (i + m >= n) break;
        }
        return -1;
    }
}