-
Notifications
You must be signed in to change notification settings - Fork 0
/
FirstOccurrenceIndex.kt
59 lines (46 loc) · 1.46 KB
/
FirstOccurrenceIndex.kt
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
59
/*
* Find the Index of the First Occurrence in a String
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack,
or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
*/
fun main(args: Array<String>) {
print(strStr("sadbutsad","sad"))
print(strStr1("sadbutsad","sad"))
print(strStr2("sadbutsed","sed"))
}
fun strStr(haystack: String, needle: String): Int {
return haystack.indexOf(needle)
}
// Brute Force - O(n*n)
fun strStr1(haystack:String, needle:String): Int {
var hLength = haystack.length
var nLength = needle.length
for(i in 0 until hLength+1 - nLength) {
for(j in 0 until nLength) {
if(haystack[i+j] != needle[j])
break
if(j == nLength - 1)
return i
}
}
return -1
}
// Sliding Window - O(n)
fun strStr2(haystack:String, needle:String): Int {
var hLength = haystack.length
var nLength = needle.length - 1
for(i in 0 until hLength - nLength) { // Do not go forward if `<nLength` char is left at the end
val subString = haystack.substring(i .. i + nLength)
if(subString == needle) return i
}
return -1
}