Listedeki bir öğenin java

Question

diğer öneki olup olmadığını kontrol edin. Dizelerin bir listesini uygulamak istiyorum ve sonra listedeki diğer öğenin öneki olan herhangi bir öğe varsa listeden tüm öğeyi denetleyin. . Yukarıdaki listede örneğin

[abc, cde, efg, cdetgh] 

için, "cde" (bir eleman) diğer elemanın "cdetgh" öneki olan. Mümkünse listeyi tekrarlamak istemiyorum.

Answer 1

Tüm listeyi yinelemek zorundasınız. Naif yaklaşım, listedeki her öğe için tüm listeyi yinelemenizi zorlayacaktır. Bu bir O (N^2) algoritmasıdır. Listenin boyutuna ve bu işlemi gerçekleştirmeniz için gereken sıklığa bağlı olarak, bu kabul edilebilir olabilir.

Alan pahasına zaman kazanmak için bir trade-off yapabilirsiniz. Her öğeye gidin ve her öğe için her önekin bir hashsetini oluşturun ve öneklerde bulunan öğeleri kontrol edin. N liste boyutu ve M, ortalama elemanı uzunluğudur

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

Bu algoritma, zaman içinde O (N * M) 'dir. Ama biraz daha yer kaplıyor. Bunun için daha da verimli çözümler var, ama giderek karmaşıklaşıyorlar ve sonlu durum makinesi yapımını veya bir önek ağacını içeriyorlar.