Actually this is not an AI problem, this is pure programming question solved by dynamic programming.
If you simply want to connect the tokens into a list of correctly spelled words then you proceed as follows (Top down style dynamic programming):
public class Connector {
public static void main(String[] args) {
List<String> tokens = new ArrayList<String>(); // input
Connector connector = new Connector();
@SuppressWarnings("unused")
List<String> ret = connector.connect(tokens);
}
Map<Integer, List<String>> cache;
List<String> tokens;
public List<String> connect(List<String> tokens) {
this.cache = new HashMap<Integer, List<String>>();
this.tokens = tokens;
List<String> ret = connect(tokens, 0);
return ret;
}
List<String> connect(List<String> tokens, int start) {
if (cache.containsKey(start)) {
return cache.get(start);
} else {
List<String> results = new ArrayList<String>();
connectHelper(tokens, start, results);
cache.put(start, results);
return results;
}
}
void connectHelper(List<String> tokens, int start, List<String> results) {
int n = tokens.size();
for(int i = start + 1; i < n; i++) {
String part = concat(tokens, start, i);
if (dictContains(part)) {
List<String> restParts = connect(tokens, i);
for(String oneRestPart : restParts) {
results.add(part + " " + oneRestPart);
}
}
}
}
static private String concat(List<String> tokens, int low, int hi) {
StringBuilder sb = new StringBuilder();
for(int i = low; i < hi; i++) {
sb.append(tokens.get(i));
}
return sb.toString();
}
}
