Implement strStr() Easy
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null)
return -1;
int m = haystack.length();
int n = needle.length();
Set<String> ns = new HashSet<String>() {{
add(needle);
}};
for (int i = 0; i < m - n + 1; ++i) {
String cur = haystack.substring(i, i + n);
if (ns.contains(cur))
return i;
}
return -1;
}
思路:取得haystack中每一个与needle等长的子串,取Hash与needle相比,然后再计算是否相等。 O(n)