Question

How to check whether a string can be segmented into a sequence of words from a dictionary in Scala

Answer 1

import scala.util.control.Breaks._

object WordBreakApp {

  def wordBreak(s: String, dict: Set[String]): Boolean = {
    val slen = s.length
    val result = Array.fill(slen + 1)(false)
    result(0) = true // empty string is always segmentable

    for (i <- 1 to slen) {
      breakable {
        for (j <- 0 until i) {
          if (result(j) && dict.contains(s.substring(j, i))) {
            result(i) = true
            break // exits the inner loop
          }
        }
      }
    }

    result(slen)
  }

  def main(args: Array[String]): Unit = {
    val dict = Set("future", "depends", "the", "on", "your", "dreams", "start", "today")
    val s = "futuredependsonyourdreams"

    if (wordBreak(s, dict))
      println("The string can be segmented")
    else
      println("The string cannot be segmented")
  }
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

object WordBreaker {

  def isInDict(word: String, dict: List[String]): Boolean = {
    dict.contains(word)
  }

  def wordBreak(str: String, result: String, dict: List[String]): Unit = {
    val strsize = str.length
    for (i <- 1 to strsize) {
      val subStr = str.substring(0, i)
      if (isInDict(subStr, dict)) {
        if (i == strsize) {
          println(result + subStr)
          return
        }
        wordBreak(str.substring(i), result + subStr + " ", dict)
      }
    }
  }

  def main(args: Array[String]): Unit = {
    val str = "butterflyplaybasketballwithbags"
    val dict = List(
      "butterfly", "basketball", "bagpiper", "and", "play",
      "with", "butter", "fly", "basket", "ball", "bags"
    )

    wordBreak(str, "", dict)
  }
}



/*
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

*/

 

70+ SQL courses for beginners and professionals