/*
Helper: check if a substring is in the dictionary.
Uses a simple array of strings and linear search.
*/
function dictContains(candidate, dict) {
return dict.includes(candidate);
}
/*
This function performs the segmentation and returns the result.
It contains your original DP logic exactly as before.
*/
function segmentText(text, dict) {
const n = text.length;
// dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid
const dp = Array(n + 1).fill(0);
const valid = Array(n + 1).fill(false);
valid[0] = true; // empty prefix is valid
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
// 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].
const candidate = text.slice(j, i);
// Verify whether this substring is a valid dictionary word.
if (dictContains(candidate, dict)) {
// Record that index j is the previous valid split before i.
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 [];
}
// Backtrack to recover words
const words = [];
let i = n;
while (i > 0) {
const j = dp[i];
words.push(text.slice(j, i));
i = j;
}
// Reverse the collected words
words.reverse();
return words;
}
/* Example usage */
const text = "thisisatestfoo";
const dict = [
"this", "is", "a", "test", "hello", "world", "foo", "bar"
];
const words = segmentText(text, dict);
console.log("Segmentation result:");
for (const w of words) {
console.log(w);
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
