A simple recursive algorithm can be implemented if you realize that the segmentation of a string s is equal to a set containing s itself, and a set union of each substring X of s with the segmentation of s\X. Also, since you will always have n-1 possible substrings, and you can either segment or not segment in each of these points, you will always end up with 2^(n-1) segments.
It is more simple to understand with an example for the segmentation of the string ABC:
- {'ABC'} // 'ABC' itself
- {'A', 'B, 'C'} // substring 'A' union 1st segmentation of 'BC' = {'B, 'C'}
- {'A', 'BC'} // substring 'A' union 2nd segmentation of 'BC' =
{'BC'}
- {'AB', 'C'} // substring 'AB' union 1st and only segmentation of 'C' =
{'C'}
- Union of 1, 2, 3, and 4, yield all segmentations of the string
ABC.
This translates almost directly to the following implementation:
public static Set<Set<String>> segment(String s) {
// `s` itself.
Set<Set<String>> result = new LinkedHashSet<Set<String>>();
Set<String> root = new LinkedHashSet<String>();
root.add(s);
result.add(root);
// set union of each substring `X` (prefix) of `s` with `s\X` (rest).
for (int i = 1; i < s.length(); i++) {
String prefix = s.substring(0, i);
String rest = s.substring(i);
for (Set<String> segments : segment(rest)) {
Set<String> segment = new LinkedHashSet<String>();
segment.add(prefix);
segment.addAll(segments);
result.add(segment);
}
}
return result;
}
Sample outputs:
System.out.println(segment("ABC"));
// [[ABC], [AB, C], [A, B, C], [BC, A]]
System.out.println(segment("ABCD"));
// [[D, AB, C], [BCD, A], [D, ABC], [D, A, B, C], [AB, CD], [ABCD], [D, BC, A], [A, B, CD]]
