¿Cómo se calculan los prefijos únicos más cortos de un conjunto de cadenas?

Question

Es un algoritmo bastante común en que analiza la línea de comandos. Dado un conjunto de nombres de opción largos predefinidos, calcule el prefijo más corto que identifica de manera única una de estas opciones. Así, por ejemplo, para las siguientes opciones:

-help 
-hostname 
-portnumber 
-name 
-polymorphic 

Ésta sería la salida:

-he 
-ho 
-por 
-n 
-pol 

estoy pensando dos posibles maneras de hacer esto - ya sea como un árbol:

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

O mediante la búsqueda de subcadenas:

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

Entonces, la pregunta es:

1. ¿Qué irías?
2. ¿Me estoy perdiendo una tercera forma obvia?

Answer 1

La solución "árbol" es un caso especial (bueno, en realidad es bastante general) de un Patricia trie.

El primero generalmente será más rápido de buscar. Las consideraciones de la memoria probablemente no sean relevantes para su contexto, ya que no se usa permanentemente y solo realiza la "búsqueda" una vez.

Answer 2

Haría el árbol, se ve bien.

Puede crear un hash de cada posible subcadena distinta.

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, sí, la respuesta que falta más obvia es utilizar una biblioteca que ya hace esto. How to parse command line arguments in Java?