Java - Array of String - проверьте, является ли какой-то элемент частью другой строки (не finidng "Duplicates")

Question

Итак, у меня есть массив String, и я хотел бы видеть, есть ли у него (содержит) другие как часть String ,

Например, рассмотрите следующий простой массив.

s[0]="Java" 
s[1]="Java Programming" 
s[2]="C Programming" 
s[3]="C Programming is Cool" 

В конце концов, я только хочу, чтобы держать

s[1]="Java Programming" 
s[3]="C Programming is Cool" 

, потому что с [1] содержит s [0] и s [3] содержит с [2].

Это мой код, чтобы обнаружить, если элемент массива содержит элемент массива с помощью метода String.Contains(), который, кажется, на самом деле основной и неэффективное ..

int startPtr = 0; 
while (startPtr < s.length-1) { 
    int tempPtr = startPtr+1; 
    while (tempPtr <= s.length-1) { 
     if (s[tempPtr].contains(s[startPtr])) { 
      //At this point, I know that I don't need s[startPtr] in result. 
      //Remove item at startPtr, if this were ArrayList or something. 
      startPtr++; 
      break; 
    } else { indexPtr++; } 
} 

И после того, как startPtr достигает конца, я думаю, что я должен делать то же самое в обратном порядке (начинать с конца и проверять на начало массива), чтобы гарантировать, что никакая строка не является частью другого строкового элемента.

Может ли кто-нибудь помочь мне с лучшим алгоритмом? Кроме того, я считаю, что это alogirthm будет иметь O (N^2), я прав?

Answer 1

Я отвечаю на это как на ответ, потому что ОП запросил дополнительную информацию о моем комментарии к ответу кметтера. Повторяю, они дают ключ к решению mapeter: он добавляет элементы в новый список, а не удаляет их из списка, гарантируя, что удаленный элемент не испортит арифметику указателя и вызовет ошибку за пределами границ.Тем не менее, это также может быть достигнуто на месте, путем перебора массива в обратном направлении:

Collections.sort(s, new LengthCompare()); 
for (int i = s.size() - 1; i >= 1; i--) 
{ 
    for (int j = i-1; j >= 0; j--) 
    { 
     if (s[j].contains(s[i])) 
     { 
      s.remove(i) 
      break; 
     } 
    } 
} 

private static class LengthCompare implements Comparator<String> 
{ 
    public int compare(String s1, String s2) 
    { 
     return (s2.length() - s1.length()); 
    } 
} 

Конечно, так как примитивные массивы имеют фиксированный размер, это только для списков (которые, не видя остальную часть кода это происходит, я не понимаю, почему вы не могли использовать его).

Кроме того, я не проверял, действительно ли это компилируется. Это просто псевдокод, и у меня могут быть смешанные типы массивов и списков, но форма остается прежней.

Answer 2

Я бы порекомендовал сортировку строк в s в порядке убывания длины в первую очередь. После этого при повторении через s каждая строка не может содержаться в более поздней строке в s, так как более поздние строки короче по длине. В результате вам нужно будет только один раз пройти через s, и вам не нужно будет выполнять какой-либо откат.

List<String> finalStrs = new ArrayList<>(); 
// You will have to create decreasingLengthComparator 
Arrays.sort(s, decreasingLengthComparator); 
for (String str : s) { 
    boolean addToFinal = true; 
    for (String finalStr : finalStrs) { 
     if (finalStr.contains(str)) { 
      addToFinal = false; 
      break; 
     } 
    } 
    if (addToFinal) { 
     finalStrs.add(str); 
    } 
} 

Эффективность сортировки - O (nlog (n)). Эффективность итерации через s и проверка наличия строк в finalStrs равна O (n^2/2) * O (время сравнения строк).

В результате общая сложность - это O (nlog (n) + n^2/2 * время для сравнения строк) = O (n^2/2 * время для сравнения строк), что является улучшением ваш алгоритм (хотя и очень небольшое улучшение, но алгоритм также проще реализовать и следовать по моему мнению).

Answer 3

Существует еще одна возможность для большого количества строк и относительно коротких строк. Сложность вычислений - O (n log (n) + n k^2 * log (n * k)), где n - количество строк, а k - длина самой длинной строки.

Идея состоит в том, чтобы создать набор поиска всех возможных подстрок строк, уже включенных в набор результатов, и проверить наличие в этом наборе.

В худшем случае вы будете иметь n * k^2/2 различные строки в наборе поиска.

TreeSet<String> containedStrings = new TreeSet<>(); 
List<String> finalStrs = new ArrayList<>(); 
// You will have to create decreasingLengthComparator 
Arrays.sort(s, decreasingLengthComparator); 
for (String str : s) 
    if (!containedStrings.contains(str)) 
     finalStrs.add(str); 
     for (int i = 0; i < s.length(); i++) 
      for (int j = i+1; j <= s.length(); j++) 
       containedStrings.add(s.substring(i, j)); 
    }