Scala algorithm: Reverse a String's words efficiently

Published

Algorithm goal

Efficiently, reverse a String's words. For example, 'Hello new world' becomes 'world new Hello'.

Explanation

While this may look a long-winded solution, it is very explicit and also streaming-based.

An efficiency portion of this algorithm comes from the fact that rather than appending every character that we come across to an existing string, and thus ending up with allocations of a new String per character, we can extract out the positions of the spaces, and come up with the shape of our target String by describing it in terms of the edges and where the spaces are. (this is © from www.scala-algorithms.com)

The rest of the Explanation is available for subscribers.

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Scala concepts & Hints

  1. Collect

    'collect' allows you to use Pattern Matching, to filter and map items.

    assert("Hello World".collect {
      case character if Character.isUpperCase(character) => character.toLower
    } == "hw")
    
  2. Pattern Matching

    Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

    assert("Hello World".collect {
      case character if Character.isUpperCase(character) => character.toLower
    } == "hw")
    
  3. Sliding / Sliding Window

    Get fixed-length sliding sub-sequences (sliding windows) from another sequence

  4. State machine

    A state machine is the use of `sealed trait` to represent all the possible states of a 'machine' in a hierarchical form

  5. View

    The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

Algorithm in Scala

34 lines of Scala (version 2.13), showing how concise Scala can be!

This solution is available for access!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Test cases in Scala

assert(reverseWords("").toList == List(""))
assert(reverseWords("A").toList == List("A"))
assert(reverseWords("AA").toList == List("AA"))
assert(reverseWords("AA BB").toList == List("BB", "AA"))
assert(reverseWords("AA  BB").toList == List("BB", "", "AA"))
assert(reverseString("cannot") == "cannot")
assert(reverseString("") == "")
assert(reverseString(" a b ") == " b a ")
assert(reverseString("AA BB") == "BB AA")
assert(reverseString("cannot do") == "do cannot")
assert(
  reverseString("cannot do without Scala") == "Scala without do cannot"
)

View the rest of Scala algorithms