import java.util.ArrayList;
import java.util.List;
public class SegmentTextJava {
/**
Helper: check if a substring is in the dictionary.
Uses a simple array of strings and linear search.
*/
static boolean dict_contains(String candidate, String[] dict) {
for (String word : dict) {
if (candidate.equals(word)) {
return true;
}
}
return false;
}
/**
This function performs the segmentation and prints the result.
It contains your original DP logic exactly as before.
*/
static void segment_text(String text, String[] dict) {
int n = text.length();
/** dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid */
int[] dp = new int[n + 1];
boolean[] valid = new boolean[n + 1];
valid[0] = true; /** empty prefix is valid */
for (int i = 1; i <= n; i++) {
valid[i] = false;
for (int 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]. */
int len = i - j;
String candidate = text.substring(j, i);
/** 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]) {
System.out.println("No valid segmentation found.");
return;
}
/** Backtrack to recover words */
List<String> words = new ArrayList<>();
int i = n;
while (i > 0) {
int j = dp[i];
int len = i - j;
String w = text.substring(j, i);
words.add(w);
i = j;
}
/** Reverse the collected words */
for (int k = 0; k < words.size() / 2; k++) {
String tmp = words.get(k);
words.set(k, words.get(words.size() - 1 - k));
words.set(words.size() - 1 - k, tmp);
}
/** Print results */
System.out.println("Segmentation result:");
for (String w : words) {
System.out.println(w);
}
}
public static void main(String[] args) {
String text = "thisisatestfoo";
/** Example dictionary */
String[] dict = {
"this", "is", "a", "test", "hello", "world", "foo", "bar"
};
/** Call the segmentation function */
segment_text(text, dict);
}
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
