Как вычислить кратчайшие уникальные префиксы набора строк?
Это довольно распространенный алгоритм при разборе командной строки . Учитывая набор предопределенных длинных имен опций - вычислите самый короткий префикс, который однозначно идентифицирует одну из этих опций. Например, для следующих опций:
-help
-hostname
-portnumber
-name
-polymorphic
Это будет вывод:
-he
-ho
-por
-n
-pol
Я думаю о двух возможных способах сделать это - либо в виде дерева:
*
/ | \
/ | \
H N P
/ \ |
E O O
/ \
R L
, либо путем поиска подстрок:
for (String s : strings) {
for (int i = 1; i < s.length(); s++) {
if (search(strings,s.substring(0,i)) == 1) {
result.add(s.substring(0,i);
break;
}
}
}
Итак, вопрос в следующем:
- Куда бы вы пошли?
- Я упускаю очевидный третий путь?
2 ответа
Решение "дерево" является частным случаем (ну, на самом деле, довольно общим) дерева Патрисии.
Первое обычно быстрее для поиска. Соображения по поводу памяти, вероятно, не имеют отношения к вашему контексту, поскольку она не используется постоянно, и вы выполняете «поиск» только один раз.
Я бы сделал дерево, выглядит нормально.
Вы можете создать хэш каждой возможной отдельной подстроки.
Hashmap<String, String> validSubs = new Hashmap<String, String>();
HashSet<String> usedSubs = new HashSet<String>();
for (String option : options) {
for(int i = 0; i <= option.length; i++) {
String sub = option.substring(0, i);
if(usedSubs.contains(sub)) {
validSubs.remove(sub);
} else {
validSubs.add(sub, option);
usedSubs.add(sub);
}
}
}