-
Notifications
You must be signed in to change notification settings - Fork 26
/
Copy path28. Implement strStr().java
executable file
·58 lines (47 loc) · 1.63 KB
/
28. Implement strStr().java
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
48
49
50
51
52
53
54
55
56
57
58
E
tags: Two Pointers, String
给两个string A, B, 找一个 B 在 A 种的起始位置.
#### Two Pointer
- 找到B在A中的起始位置, 然后看一下从这个点开始的substring是否等于B就可以了
- 还挺多坑的, 这些可以帮助优化:
- 1. 当B是“”的时候,也就是能在A的其实位置找到B....index = 0.
- 2. edge condition: 如果 haystack.length() < needle.length() 的话, 必须错, return -1
- 3. 如果在某个index, A后面剩下的长度, 比B的长度短, 也是误解, return -1
```
/*
Implement strStr().
Returns the index of the first occurrence of needle in haystack,
or -1 if needle is not part of haystack.
Hide Company Tags Facebook
Hide Tags Two Pointers String
Hide Similar Problems (H) Shortest Palindrome
Clarification
Do I need to implement KMP Algorithm in an interview?
- Not necessary. When this problem occurs in an interview,
the interviewer just want to test your basic implementation ability.
*/
class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.length() == 0) {
return 0;
}
if (needle.length() > haystack.length()) {
return -1;
}
int n = haystack.length();
int m = needle.length();
for (int i = 0; i < n; i++) { // n(n)
if (n - i < m) {
return -1;
}
if (haystack.charAt(i) != needle.charAt(0)) {
continue;
}
if (haystack.substring(i, i + m).equals(needle)) { // O(m)
return i;
}
}
return -1;
}
}
```