Простой рекурсивный алгоритм может быть реализован, если вы понимаете, что сегментация строки s равна набору, содержащему s, и объединению наборов каждой подстроки X из s с сегментациейs\X.Кроме того, поскольку у вас всегда будет n-1 возможных подстрок, и вы можете сегментировать или не сегментировать в каждой из этих точек, у вас всегда будет 2^(n-1) сегментов.
Это проще понять на примере сегментации строки ABC:
- {'ABC'} // сама 'ABC'
- {'A', 'B,' C '} // подстрока' A 'объединение 1-я сегментация' BC '= {' B, 'C'}
- {'A', 'BC '} // подстрока' A ', объединение 2-й сегментации' BC '= {' BC '}
- {' AB ',' C '} // подстрока' AB ', объединение 1-й и только сегментация'C '= {' C '}
- Объединение 1, 2, 3 и 4, дает все сегментации строки
ABC.
Это переводит почтинепосредственно к следующей реализации:
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;
}
Пример выходных данных:
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]]