Scala algorithm: Find the index of a substring ('indexOf')
Reimplement the 'String#indexOf' Java function.
Test cases in Scala
assert(indexOf("Test", "ested") == None) assert(indexOf("Test", "ested1234") == None) assert(indexOf("Test", "est") == Some(1)) assert(indexOf("Tesla Test", "est") == Some(7)) assert(indexOf("est", "est") == Some(0)) assert(indexOf("es", "est") == None)
Algorithm in Scala
11 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!
Note that we do not need to check all of the positions of the string - this can be shown by considering where the needle/target string could possibly end.
Then, by using a View, we can compute the tails of the input string, coupled with their start index; If the tail equals to the search string, we found our result - so we return the first such a result. (this is © from www.scala-algorithms.com)
Scala concepts & Hints
Drop, Take, dropRight, takeRight
Scala's `drop` and `take` methods typically remove or select `n` items from a collection.
The for-comprehension is highly important syntatic enhancement in functional programming languages.
The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
.viewsyntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.
'zip' allows you to combine two lists pair-wise (meaning turn a pair of lists, into a list of pairs)
It can be used over Arrays, Lists, Views, Iterators and other collections.