/*
Helper: check if a substring is in the dictionary.
Uses a simple array of strings and linear search.
*/
func dictContains(_ candidate: String, _ dict: [String]) -> Bool {
return dict.contains(candidate)
}
/*
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] {
let n: Int = text.count
let chars: [Character] = Array(text)
// dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid
var dp: [Int] = Array(repeating: 0, count: n + 1)
var valid: [Bool] = Array(repeating: false, count: n + 1)
valid[0] = true // empty prefix is valid
for i in 1...n {
for j in 0..<i {
// Check whether dp[j] contains a valid split point;
if valid[j] {
// Create substring text[j:i]
let candidate = String(chars[j..<i])
// Verify whether this substring is a valid dictionary word.
if dictContains(candidate, dict) {
dp[i] = j
valid[i] = true
break // found a valid segmentation ending at i
}
}
}
}
// If dp[n] is not valid, segmentation is impossible
if !valid[n] {
return []
}
// Backtrack to recover words
var words: [String] = []
var idx: Int = n
while idx > 0 {
let j = dp[idx]
let w = String(chars[j..<idx])
words.append(w)
idx = j
}
// Reverse the collected words
return words.reversed()
}
/* Example usage */
let text = "thisisatestfoo"
let dict = [
"this", "is", "a", "test", "hello", "world", "foo", "bar"
]
let words = segmentText(text, dict)
print("Segmentation result:")
for w in words {
print(w)
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
