Как вычислить кратчайшие уникальные префиксы из набора строк?

Question

Это довольно распространенный алгоритм при разборе командной строки .Учитывая набор предопределенных длинных имен опций - вычислите самый короткий префикс, который однозначно идентифицирует одну из этих опций.Например, для следующих опций:

-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;
      }
   }
}

Итак, вопрос в следующем:

1. Что бы вы выбрали?
2. Я пропускаю очевидный третий путь?

Answer 1

«Древовидное» решение - это особый случай (ну, на самом деле, он довольно общий) для Патрисии Три .

Первый обычно будет быстрее искать. Вопросы памяти, вероятно, не имеют отношения к вашему контексту, поскольку он не используется постоянно, и вы выполняете «поиск» только один раз.

Answer 2

О, да, самый очевидный пропущенный ответ - использовать библиотеку, которая уже делает это. Как разобрать аргументы командной строки в Java?

Answer 3

Я бы сделал дерево, выглядит хорошо.

Вы можете создать хеш из каждой возможной отдельной подстроки.

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);
    }
  }
}