Poison

28. Find the Index of the First Occurrence in a String

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int strStr(String haystack, String needle) {
        char firstChar = needle.charAt(0);
        int i = 0;
        while (i <= haystack.length() - needle.length()) {
            if (haystack.charAt(i) == firstChar) {
                int j = i + 1, k = 1;
                while (k < needle.length() && haystack.charAt(j) == needle.charAt(k)) {
                    j++;
                    k++;
                }
                if (k == needle.length()) {
                    return i;
                }
            }

            i++;
        }

        return -1;
    }
}

以上参考 JDK 中 String#indexOf 实现，相比暴力解法效率更优，主要利用了首个字符匹配。

Reference

28. Find the Index of the First Occurrence in a String
Why does String.indexOf() not use KMP? - Stack Overflow
efficiency - Why does Java’s String class not implement a more efficient indexOf()? - Software Engineering Stack Exchange