I hope you had a good weekend (and Monday) I didn't have the time to write the posts of this weekend but I did have the time to code...so there is day 5 !!
Details
- Asked by: Dropbox
- Difficulty: Hard
Problem
Implement an efficient string matching algorithm.
Given a string of length N
and a pattern of length k
, write a program that searches for the pattern in the string with less than O(N * k)
worst-case time complexity.
If the pattern is found, return the start index of its location. If not, return False
.
My solution
Nothing really special about this one. Sadly, because of the ".length" I'm not under O(N*k).
/**
* Search pattern into searchIn
*
* @param searchIn
* @param pattern substring to find in searchIn
* @return start index in string of the pattern, null if not found
*/
fun find(searchIn: String, pattern: String): Int? {
for (i in 0 until searchIn.length - pattern.length){
for ((index, c) in pattern.withIndex()){
if (searchIn[i + index] != c)
break
else if(index == pattern.length - 1)
return i
}
}
return null
}
Now I have a class, so see you tomorrow! 😃
Top comments (0)