Verifica se un elemento nell'elenco è prefisso di altro in java

Question

Voglio implementare un elenco di stringhe e quindi controllare per tutti gli elementi nell'elenco che se c'è un elemento che è il prefisso dell'altro elemento nell'elenco o no . Ad esempio

[abc, cde, efg, cdetgh] 

in questo elenco, "cde" (un elemento) è prefisso altro elemento "cdetgh". Non voglio ripetere l'intera lista, se possibile.

Answer 1

È necessario ripetere l'intera lista. L'approccio ingenuo ti costringerà a ripetere l'intera lista per ogni elemento della lista. Questo è un algoritmo O (N^2).

A seconda della dimensione dell'elenco e della frequenza necessaria per eseguire questa operazione, ciò potrebbe essere accettabile. Puoi fare un compromesso per risparmiare tempo a scapito dello spazio. Passare attraverso ogni elemento, e creare un hashset di ogni prefisso per ogni elemento, e quindi vedere controllare gli elementi che sono nei prefissi.

final Map<String, List<String>> prefixes = new HashMap<>(); 
for (final String element : list) { 
    // Go through every prefix that is at least 1 in length, 
    // but shorter than the current element). 
    for (int len = 1; len < element.length() - 1; ++len) { 
     final String prefix = element.substring(0, len); 
     List<String> hasPrefix = prefixes.get(prefix); 
     if (hasPrefix == null) { 
      hasPrefix = new ArrayList<>(); 
      prefixes.put(prefix, hasPrefix); 
     } 
     hasPrefix.add(element); 
    } 
} 

for (final String element : list) { 
    if (prefixes.containsKey(element)) { 
     System.out.printf("The element \"%s\" is a prefix of the following elements:\n%s", element, prefixes.get(element).toString()); 
    } 
} 

Questo algoritmo è O (N * M) nel tempo, dove N è la dimensione lista, e M è la lunghezza media elemento. Ma occupa un po 'più di spazio. Ci sono soluzioni ancora più efficienti a questo, ma diventano sempre più complesse e coinvolgono la costruzione di macchine a stati finiti o un albero di prefissi.