package main
import (
"fmt"
)
/*
Helper: check if a substring is in the dictionary.
Uses a simple slice of strings and linear search.
*/
func dictContains(candidate string, dict []string) bool {
for _, word := range dict {
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.
*/
func segmentText(text string, dict []string) []string {
n := len(text)
// dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid
dp := make([]int, n+1)
valid := make([]bool, n+1)
valid[0] = true // empty prefix is valid
for i := 1; i <= n; i++ {
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].
candidate := text[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 []string{}
}
// Backtrack to recover words
words := []string{}
idx := n
for idx > 0 {
j := dp[idx]
w := text[j:idx]
words = append(words, w)
idx = j
}
// Reverse the collected words
for i := 0; i < len(words)/2; i++ {
words[i], words[len(words)-1-i] = words[len(words)-1-i], words[i]
}
return words
}
func main() {
text := "thisisatestfoo"
// Example dictionary
dict := []string{
"this", "is", "a", "test", "hello", "world", "foo", "bar",
}
words := segmentText(text, dict)
fmt.Println("Segmentation result:")
for _, w := range words {
fmt.Println(w)
}
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
