/*
Helper: check if a substring is in the dictionary.
Uses a simple list of strings and linear search.
*/
fun dictContains(candidate: String, dict: List<String>): Boolean {
return candidate in dict
}
/*
This function performs the segmentation and returns the result.
It contains your original DP logic exactly as before.
*/
fun segmentText(text: String, dict: List<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: MutableList<Int> = MutableList(n + 1) { 0 }
val valid: MutableList<Boolean> = MutableList(n + 1) { false }
valid[0] = true // empty prefix is valid
for (i in 1..n) {
for (j in 0 until 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.
break
}
}
}
}
// If dp[n] is not valid, segmentation is impossible
if (!valid[n]) return emptyList()
// Backtrack to recover words
val words: MutableList<String> = mutableListOf()
var idx: Int = n
while (idx > 0) {
val j: Int = dp[idx]
val w: String = text.substring(j, idx)
words.add(w)
idx = j
}
// Reverse the collected words
words.reverse()
return words
}
fun main() {
val text: String = "thisisatestfoo"
// Example dictionary
val dict: List<String> = listOf(
"this", "is", "a", "test", "hello", "world", "foo", "bar"
)
val words: List<String> = segmentText(text, dict)
println("Segmentation result:")
words.forEach { println(it) }
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
