Палиндром в массиве строк

Question

Вам предоставляется массив строк. Вам нужно узнать общее количество пар (a, b), так что a и b являются палиндромами. Пример: html, xml, lmth, css, lmx, xhtml. Здесь общее количество пар = 2, потому что пары (html, lmth) & (xml, lmx) являются палиндромными парами. Подход грубой силы представляет собой решение O (n^2).

for(int i = 0; i < N; i++) 
{   
    for(int j = i + 1; j < N; j++) 
    { 
     StringBuffer sb = new StringBuffer(a[j]); 
     sb = sb.reverse(); 

     if(a[i].equals(sb.toString())) 
      count++; 
    } 
} 

Программа замедляется с увеличением N. Итак, что является самым эффективным способом поиска палиндромных пар, так что сложность времени равна < O (n^2).

Answer 1

Я хотел бы использовать два набора, содержащих строку и ее обращенную форму, как это следует (я буду стараться повторно использовать код):

Set<String> def = new HashSet<String>(); 
Set<String> rev = new HashSet<String>(); 

for(int i = 0; i < N; i++) { 
    StringBuffer sb = new StringBuffer(a[i]); 
    sb.reverse(); 
    String srev = sb.toString(); 

    if(rev.contains(a[i]) || def.contains(srev)) 
     ++count; 

    def.add(a[i]); 
    rev.add(srev); 
} 

Сложность еще возрастает с N, потому что вы должны посетить каждая строка не реже одного раза, но это уже не квадрат N.

В любом случае, даже код ниже должен работать. Я объясню, почему через несколько минут.

Set<String> set = new HashSet<String>(); 

for(int i = 0; i < N; i++) { 
    StringBuffer sb = new StringBuffer(a[i]); 

    if(set.contains(sb.reverse().toString())) 
     ++count; 

    set.add(a[i]); 
} 

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

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

Это решение имеет проблемы, если у вас есть такие массивы, как: [xml, lmx, lmx], но я не знаю, что вы ожидаете в этих случаях (в любом случае вы можете использовать мульти-набор или хэш-карту и удалять элементы из набора для достижения разных результатов).

Answer 2

В дополнение к skypjack ответ, и предоставить другой алгоритм (и сравнение), здесь дихотомическая поиск:

private static int countDichotomic (String[] a) { 
    int count = 0 ; 
    Arrays.sort(a) ; 

    for(int i = 0; i < a.length; i++) { 
     StringBuffer sb = new StringBuffer(a[i]); 
     sb.reverse(); 
     if (Arrays.binarySearch(a, i + 1, a.length, sb.toString()) > i) 
      count ++ ; 
    } 
    return count ; 
} 

Я явно не Java developper так простите мой плохой стиль кодирования ...

Вот некоторые результаты от 3 метода:

N = 10000 
Original: 2113ms 
HashSet: 7ms 
Dichotomic: 10ms 

N = 100000 
Original: Unknow (too long) 
HashSet: 83ms 
Dichotomic: 147ms 

N = 1000000 
Original: Unknow (too long) 
HashSet: 1137ms 
Dichotomic: 1951ms 

Важное примечание: Эти повторные sults для строки длиной 20, что коротко. Разница между методами HashSet и Dichotomic становится короче и короче, чем длина строки increse. На моем компьютере Dichotomic метод достигает HashSet для длины строки о 1000, и разрыв между этими двумя возрастает с увеличением длины строки:

N = 100000 
L = 20 
HashSet: 83ms 
Dichotomic: 147ms 
L = 100 
HashSet: 115ms 
Dichotomic: 167ms 
L = 300 
HashSet: 169ms 
Dichotomic: 238ms 
L = 500 
HashSet: 262ms 
Dichotomic: 319ms 
L = 1000 
HashSet: 384ms 
Dichotomic: 386ms 
L = 5000 
HashSet: 1866ms 
Dichotomic: 895ms 

Код я использовал для вычисления времени:

long startTime, endTime, count = 0 ; 
double duration ; 
startTime = System.nanoTime(); 
count = countMethod (arrayOfStrings); 
endTime = System.nanoTime(); 
duration = (endTime - startTime)/1000000 ; 
System.out.println("Original: " + count + ", " + duration + "ms"); 

I используйте рандомизированные строки, поэтому я получаю общее количество 0 (смотря на алгоритм, я не думаю, что это изменит результат).Тем не менее, я не эксперт по Java, поэтому может быть лучший способ выполнять эти функции.

Важное примечание: я вычислил время только один экземпляр, который не очень точен, но результаты я, в стране насчитывается не много различие между 2 случаями (и я didnot есть время, чтобы написать действительно точная программа ...).

Вот весь код:

import java.util.Arrays; 
import java.util.HashSet; 
import java.util.Random; 
import java.util.Set; 

public class PalindromeSearch { 

    private static String random() { 
     char[] chars = "abcdefghijklmnopqrstuvwxyz".toCharArray(); 
     StringBuilder sb = new StringBuilder(); 
     Random random = new Random(); 
     for (int i = 0; i < 20; i++) { 
      char c = chars[random.nextInt(chars.length)]; 
      sb.append(c); 
     } 
     return sb.toString(); 
    } 

    private static int N_String = 1000000 ; 

    private static int countOriginal (String[] a) { 
     int count = 0 ; 
     for(int i = 0; i < a.length; i++) 
     {   
      for(int j = i + 1; j < a.length; j++) 
      { 
       StringBuffer sb = new StringBuffer(a[j]); 
       sb = sb.reverse(); 

       if(a[i].equals(sb.toString())) 
        count++; 
      } 
     } 
     return count ; 
    } 

    private static int countHashSet (String[] a) { 
     int count = 0 ; 
     Set<String> def = new HashSet<String>(); 
     Set<String> rev = new HashSet<String>(); 

     for(int i = 0; i < a.length; i++) { 
      StringBuffer sb = new StringBuffer(a[i]); 
      sb.reverse(); 
      String srev = sb.toString(); 

      if(rev.contains(a[i]) || def.contains(srev)) 
       ++count; 

      def.add(a[i]); 
      rev.add(srev); 
     } 
     return count ; 
    } 

    private static int countDichotomic (String[] a) { 
     int count = 0 ; 
     Arrays.sort(a) ; 

     for(int i = 0; i < a.length; i++) { 
      StringBuffer sb = new StringBuffer(a[i]); 
      sb.reverse(); 
      if (Arrays.binarySearch(a, i + 1, a.length, sb.toString()) > i) 
       count ++ ; 
     } 
     return count ; 
    } 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     String[] arrayOfStrings = new String[N_String] ; 
     for (int i = 0 ; i < arrayOfStrings.length ; i++) { 
      arrayOfStrings[i] = random() ; 
     } 

     // arrayOfStrings = new String[] {"html", "xml", "lmth", "css", "lmx", "xhtml"} ; 

     long startTime, endTime, count = 0 ; 
     double duration ; 
     startTime = System.nanoTime(); 
     // count = countOriginal (arrayOfStrings); 
     endTime = System.nanoTime(); 
     duration = (endTime - startTime)/1000000 ; //divide by 1000000 to get milliseconds. 
     System.out.println("Original: " + count + ", " + duration + "ms"); 

     startTime = System.nanoTime(); 
     count = countHashSet(arrayOfStrings); 
     endTime = System.nanoTime(); 
     duration = (endTime - startTime)/1000000 ; //divide by 1000000 to get milliseconds. 
     System.out.println("HashSet: " + count + ", " + duration + "ms"); 

     startTime = System.nanoTime(); 
     count = countDichotomic(arrayOfStrings); 
     endTime = System.nanoTime(); 
     duration = (endTime - startTime)/1000000 ; //divide by 1000000 to get milliseconds. 
     System.out.println("Dichotomic: " + count + ", " + duration + "ms"); 
    } 

}