题目介绍 Implement strStr()
.
Return the index of the first occurrence of needle in haystack, or -1
if needle
is not part of haystack
.
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()
.
示例 Example 1:1 2 Input: haystack = "hello", needle = "ll" Output: 2
Example 2:1 2 Input: haystack = "aaaaa", needle = "bba" Output: -1
Example 3:1 2 Input: haystack = "", needle = "" Output: 0
题解 字符串比较其实是写代码里永恒的主题,底层的编译器等处理肯定需要字符串对比,像 kmp 算法也是很厉害
code 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 36 37 38 39 40 41 42 43 44 45 46 47 public int strStr (String haystack, String needle) { if (haystack == null || needle == null ) { return -1 ; } if (haystack.length() < needle.length()) { return -1 ; } if (needle.equals("" )) { return 0 ; } if (haystack.equals(needle)) { return 0 ; } int needleLength = needle.length(); int haystackLength = haystack.length(); for (int i = needleLength - 1 ; i <= haystackLength - 1 ; i++) { if (needle.charAt(needleLength - 1 ) == haystack.charAt(i)) { if (needle.length() == 1 ) { return i; } boolean flag = true ; int j = needle.length() - 2 ; for (; j >= 0 ; j--) { if (needle.charAt(j) != haystack.charAt(i - (needleLength - j) + 1 )) { flag = false ; break ; } } if (flag) { return i - needleLength + 1 ; } } } return -1 ; }