object SegmentTextScala {
/*
Helper: check if a substring is in the dictionary.
Uses a simple sequence of strings and linear search.
*/
def dictContains(candidate: String, dict: Seq[String]): Boolean =
dict.contains(candidate)
/*
This function performs the segmentation and returns the result.
It contains your original DP logic exactly as before.
*/
def segmentText(text: String, dict: Seq[String]): List[String] = {
val n: Int = text.length
// dp(i) = index j such that text[j:i] is a valid word and dp(j) is valid
val dp: Array[Int] = Array.fill(n + 1)(0)
val valid: Array[Boolean] = Array.fill(n + 1)(false)
valid(0) = true // empty prefix is valid
for (i <- 1 to n) {
for (j <- 0 until i if !valid(i)) {
// Check whether dp(j) contains a valid split point;
// if it does, it means the prefix text[0:j] can be segmented.
if (valid(j)) {
// Create a lightweight substring representing text[j:i].
val candidate: String = text.substring(j, i)
// Verify whether this substring is a valid dictionary word.
if (dictContains(candidate, dict)) {
dp(i) = j
valid(i) = true
// Stop searching for other j values because we already found
// a valid segmentation ending at i.
}
}
}
}
// If dp(n) is not valid, segmentation is impossible
if (!valid(n)) return List.empty
// Backtrack to recover words
var words: List[String] = Nil
var idx: Int = n
while (idx > 0) {
val j: Int = dp(idx)
val w: String = text.substring(j, idx)
words = w :: words
idx = j
}
words
}
def main(args: Array[String]): Unit = {
val text: String = "thisisatestfoo"
// Example dictionary
val dict: Seq[String] = Seq(
"this", "is", "a", "test", "hello", "world", "foo", "bar"
)
val words: List[String] = segmentText(text, dict)
println("Segmentation result:")
words.foreach(println)
}
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
