Comment calculer les préfixes uniques les plus courts d'un ensemble de chaînes?

Question

C'est un algorithme assez commun dans l'analyse de la ligne de commande. Étant donné un ensemble de noms d'options longs prédéfinis, calculez le préfixe le plus court qui identifie de façon unique l'une de ces options. Ainsi, par exemple, pour les options suivantes:

-help 
-hostname 
-portnumber 
-name 
-polymorphic 

Ce serait la sortie:

-he 
-ho 
-por 
-n 
-pol 

Je pense deux façons de le faire - soit comme un arbre:

   * 
      /| \ 
      /| \ 
      H N P 
     /\  | 
     E O  O 
       /\ 
       R L 

ou en recherchant des sous-chaînes:

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

Donc, la question est:

1. Qui iriez-vous?
2. Ai-je manqué une troisième voie évidente?

Answer 1

La solution "arbre" est un cas particulier (enfin, c'est plutôt général) d'un Patricia trie.

Le premier sera généralement plus rapide à rechercher. Les considérations relatives à la mémoire ne sont probablement pas pertinentes dans votre contexte, car elles ne sont pas utilisées de façon permanente et vous ne faites qu'une seule fois la "recherche".

Answer 2

Je ferais l'arbre, ça a l'air bien.

Vous pouvez créer un hachage de toutes les sous-chaînes possibles.

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

Answer 3

Oh, oui, la réponse manquante la plus évidente est d'utiliser une bibliothèque qui le fait déjà. How to parse command line arguments in Java?