/*
Helper: check if a substring is in the dictionary.
Uses a simple array of strings and linear search.
*/
function dict_contains(string $candidate, array $dict): bool {
foreach ($dict as $word) {
if ($candidate === $word) {
return true;
}
}
return false;
}
/*
This function performs the segmentation and returns the result.
It contains your original DP logic exactly as before.
*/
function segment_text(string $text, array $dict): array {
$n = strlen($text);
/* dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid */
$dp = array_fill(0, $n + 1, 0);
$valid = array_fill(0, $n + 1, false);
$valid[0] = true; /* empty prefix is valid */
for ($i = 1; $i <= $n; $i++) {
$valid[$i] = false;
for ($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]. */
$len = $i - $j;
$candidate = substr($text, $j, $len);
/* Verify whether this substring is a valid dictionary word. */
if (dict_contains($candidate, $dict)) {
/* Record that index j is the previous valid split before i.
This means text[j:i] is a valid word and dp[j] was valid. */
$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 []; // return empty array
}
/* Backtrack to recover words */
$words = [];
$i = $n;
while ($i > 0) {
$j = $dp[$i];
$len = $i - $j;
$w = substr($text, $j, $len);
$words[] = $w;
$i = $j;
}
/* Reverse the collected words */
$words = array_reverse($words);
/* Return results */
return $words;
}
/* Example usage */
$text = "thisisatestfoo";
/* Example dictionary */
$dict = [
"this", "is", "a", "test", "hello", "world", "foo", "bar"
];
/* Call the segmentation function */
$words = segment_text($text, $dict);
/* Print results */
echo "Segmentation result:\n";
foreach ($words as $w) {
echo $w . "\n";
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
