vkostyukov / scalacaster Goto Github PK

matchRabinKarp( "\"123456\"", "123456") = -1
matchRabinKarp( "\"aaaaaa\"", "aaaaaa") = -1
matchRabinKarp( "??????\"beebop\"??????????????", "beebop") = -1

(6 until 60 by 6).map( n => matchRabinKarp("\"" + "c"*n + "\"", "c"*n )) = Vector( -1, -1, ... -1 )

There are a couple of functions that could easily be rewritten to make them tail recursive, which of course would make stack overflows impossible. For example, isPalindrome().

Checking the isPalindrome... The classic algorithms are expressed as an "character-by-character algorithm", and is fine. Is oriented to a low-level view of algoritms and data-structures.

Another classic manner to view pattern-recognition algoritms in strings, is to express it by regular expression

• isPalindrome() by "anchored recursive" regular expression ^((.)(?:(?1)|.?)\2)$

• containsPalindrone() by recursive regular expression, supposing only letters (\w)(?:(?R)|\w?)\1

It is a good view from a first abstraction layer of strings... And is also classic.

The best layer for an algorithm perhaps is where the simplest and faster algorithm is expressed. It is also "classic". In the isPalindrome() an intermediary layer of abstraction, the ideal to express the same algorithm, is by use the string.reverse() method to compare strings.

Consider following example:
Asking for selectionSearch(List(5, 8, 4, 7, 3, 0, 1, 9, 6, 2), 10) should yield None, since there is no 10th element in 0-indexed list with 10 elements.

However, this call will return Some(9), which is a symptom of the bug in here:

def search(t: (List[A], A, List[A]), m: Int): Option[A] = t match {
    case (Nil, p, Nil) => Some(p)
    case (l, p, g) => select(l, p, g, l.length, m)
}

If you consider the call on singleton list with m outside range it will look like this:
search((Nil, 9, Nil), 1)

Which will return Some(9), even though m is outside the range.

The fix is to use the first pattern with guard if m == 0 and have the one without it that returns None:

def search(t: (List[A], A, List[A]), m: Int): Option[A] = t match {
    case (Nil, p, Nil) if m == 0 => Some(p)
    case (Nil, p, Nil) => None
    case (l, p, g) => select(l, p, g, l.length, m)
}

Strings.longestCommonSubstring gives incorrect results if the first string is shorter than the second one, because it only scans until the length of the first string:

object Strings {
...

def longestCommonSubstring(a: String, b: String) : String = {
def loop(m: Map[(Int, Int), Int], bestIndices: List[Int], i: Int, j: Int) : String = {
if (i > a.length) {
b.substring(bestIndices(1) - m((bestIndices(0),bestIndices(1))), bestIndices(1))
...

Doesn't work:
scala> val lcs = Strings.longestCommonSubstring("the price Is right", "right on!")
lcs: String = ri

Works correctly:
scala> val lcs = Strings.longestCommonSubstring("right on!", "the price is right")
lcs: String = right

  /**
   * Converts this tree into the string representation.
   *
   * Time - O(n)
   * Space - O(log n)
   */
  override def toString: String = 
    if (isEmpty) "."
    else "{" + left + value + right + "}"

hi, I learned a lot from your code. thanks.
IN the Tree data structure, the toString method is not visual friendly. why not just paint a tree use diagram.