Самый простой способ проверить, состоит ли строка из уникальных символов?

Question

Мне нужно проверить в Java, состоит ли слово из уникальных букв (без учета регистра). Поскольку прямое решение скучно, я придумал:

1. Для каждого символа в строке проверьте, если indexOf(char) == lastIndexOf(char).
2. Добавьте все символы в HashSet и проверьте, установлен ли размер == длина строки.
3. Преобразование строки в массив символов, сортировка по алфавиту, циклический просмотр элементов массива и проверка, если c[i] == c[i+1].

В настоящее время я люблю # 2 больше всего, кажется, самый простой способ. Какие-нибудь другие интересные решения?

Answer 1

Мне не нравится 1. - это алгоритм O (N ² ). Ваш 2. примерно линейный, но всегда пересекает всю строку. Ваш 3. - O (N lg ₂ N), с (вероятно) относительно высокой константой - вероятно, почти всегда медленнее, чем 2.

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

Редактировать: оба комментария верны, и то, какая именно часть строки, которую вы ожидаете отсканировать, будет зависеть от распределения и длины - в какой-то момент строка достаточно длинная, чтобы повторение было неизбежным если не считать этого, шанс все еще довольно высок. Фактически, с учетом плоского случайного распределения (т. Е. Все символы в наборе одинаково вероятны), это должно соответствовать парадоксу дня рождения, то есть вероятность столкновения связана с корнем квадратным из числа возможных символов в набор символов. Например, если бы мы предполагали базовый US-ASCII (128 символов) с равной вероятностью, мы бы достигли 50% -ной вероятности столкновения при 14 символах. Конечно, в реальных строках мы, вероятно, могли бы ожидать этого раньше, поскольку в большинстве строк символы ASCII не используются с частотой, близкой к одинаковой частоте.

Answer 2

Вариант 2 - лучший из трех - хеширование выполняется быстрее, чем поиск.

Однако есть еще более быстрый метод, если у вас достаточно памяти для него.

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

Например, если вы используете однобайтовые символы, есть только 256 возможностей. Вам нужно всего лишь 256 бит, чтобы отслеживать, как вы читаете строку. Если встречается символ 0x00, переверните первый бит. Если встречается символ 0x05, переверните шестой бит и т. Д. Когда встречается уже перевернутый бит, строка не уникальна.

Это худший случай O (min (n, m)), где n - длина строки, а m - размер набора символов.

И, конечно же, как я заметил в комментарии другого человека, если n> m (т.е. длина строки> размер набора символов), то по принципу "голубиного отверстия" существует повторяющийся символ, определяемый в O (1) время.

Answer 3

Под «уникальными буквами» вы подразумеваете просто стандартный английский набор из 26 или вы допускаете интересный Юникод? Какой результат вы ожидаете, если строка содержит не буквы?

Если вы рассматриваете только 26 возможных букв и хотите либо игнорировать любую не-букву, либо считать ее автоматической ошибкой, лучшим алгоритмом, вероятно, будет этот псевдокод:

create present[26] as an array of booleans.
set all elements of present[] to false.
loop over characters of your string
  if character is a letter
    if corresponding element of present[] is true
      return false.
    else
      set corresponding element of present[] to true.
    end if
  else
    handle non-letters
  end if
end loop

Единственный оставшийся вопрос - должен ли ваш массив быть массивом (требующим 26 операций для обнуления) или битовым полем (возможно, требующим больше работы для проверки / установки, но может быть обнулен в одной операции). Я думаю, что доступ к битовым полям будет в значительной степени сопоставим с поиском в массиве, если не быстрее, поэтому я ожидаю, что битовое поле - правильный ответ.

Answer 4

Мне нравится идея HashSet. Это концептуально просто, и только один проходит через строку. Для простого улучшения производительности, проверьте возвращаемое значение add . Одна вещь, о которой вы должны знать, это то, что это работает путем складывания регистра. в одном направлении. Вы можете создать класс-оболочку для Character с различной семантикой equals, чтобы он действительно чувствителен к регистру.

Интересно, что у Apache Commons есть CaseInsensitiveMap ( src ), который работает в верхнем и нижнем регистре ключа. Как вы, наверное, знаете, Java HashSet поддерживается HashMap.

public static boolean allUnique(String s)
{
  // This initial capacity can be tuned.
  HashSet<Character> hs = new HashSet<Character>(s.length());
  for(int i = 0; i < s.length(); i++)
  {
    if(!hs.add(s.charAt(i).toUpperCase())
      return false;
  }
  return true;
}

Answer 5

Сначала проверьте, является ли размер строки <= 26. Если нет, строка имеет дубликаты. вернуть В противном случае попробуйте добавить в HashSet, если это не удастся, строка вернет дубликаты. если размер HashSet is = размер строки строка имеет уникальные символы. Если нам не разрешено использовать какую-либо другую структуру данных, а также внутренние методы строки, и мы все равно должны делать это в O (n), то цикл через String.if i! = MyLastIndexof (i) возвращает Duplicates. </p>

Answer 6

Я бы предложил вариант (2) - использовать массив флагов "уже увиденных символов" вместо хэш-набора. Когда вы перебираете строку, немедленно выходите, если текущий символ уже виден.

Если у вас есть класс bitvector (я забыл, есть ли в Java), вы можете использовать его, хотя экономия памяти не обязательно приведет к какому-либо улучшению скорости и может легко замедлить процесс.

Это O (n) наихудший случай, хотя и может иметь гораздо лучшую среднюю производительность в зависимости от ваших струн - вы можете обнаружить, что большинство из них имеют повтор в начале. На самом деле, строго говоря, в любом случае это O (1) худший случай, так как строка, длина которой превышает размер набора символов , должна иметь повторяющиеся символы, поэтому у вас есть постоянная привязка к количеству символов, которые необходимо проверить в каждой строке.

Answer 7

public boolean hasUniqChars(String s){
  Hashset h = new Hashset();
  HashSet<Character> h = new HashSet<Character>();
  for (char c : s.toCharArray()) {
  if (!h.add(Character.toUpperCase(c))) // break if already present
    return false;
  }
  return true;
}

Вы должны использовать технику хэш-набора, если вы выполняете наборы символов, такие как utf-8 и ради интернационализации.

Javadoc на Character.toUpperCase для случаев использования utf: Этот метод (toUpperCase (char)) не может обрабатывать дополнительные символы. Для поддержки всех символов Юникода, включая дополнительные символы, используйте метод toUpperCase (int).

Answer 8

Как насчет использования int для хранения битов, соответствующих индексу буквы алфавита? или, может быть, длинный, чтобы иметь возможность достичь 64 различных символов.

long mask;
// already lower case
string = string.toLowerCase();
for (int i = 0; i < string.length(); ++i)
{
  int index = 1 << string.charAt(i) - 'a';
  if (mask & index == index)
    return false;

  mask |= index;
}
return true;

Это должно быть

Answer 9

Улучшение варианта 2 заключается в проверке логического флага, возвращаемого методом добавления HashSet. Это правда, если объект еще не был там. Тем не менее, чтобы этот метод был вообще полезен, сначала нужно установить строку со всеми прописными или строчными буквами.

Answer 10

           import java.io.*;

                   class unique
                  {
                           public static int[] ascii(String s)
                           {
                                    int length=s.length();
                                    int asci[] = new int[length];
                                    for(int i=0;i<length;i++)
                                    {
                                              asci[i]=(int)s.charAt(i);
                                     }
                              return asci;
                            }
                            public static int[] sort(int a[],int l)
                           {
                                       int j=1,temp;
                                       while(j<=l-1)
                                       {
                                                 temp = a[j];
                                                  int k=j-1;
                                                  while(k>=0 && temp<a[k])
                                                 {
                                                           a[k+1]= a[k];
                                                           k--;
                                                 }
                                                a[k+1]=temp;
                                                j++;
                                       } 
                           return a;
                    }
              public static boolean compare(int a[])
            { 
                     int length=a.length;
                     int diff[] = new int[length-1];
                     boolean flag=true;
                     for(int i=0;i<diff.length;i++)
                    {
                             diff[i]=a[i]-a[i+1];
                             if(diff[i]==0)
                             {
                                        flag=false;
                                        break;
                             }
                             else
                             {
                                      flag=true;
                             }
                     }
                     return flag;
                }
                public static void main(String[] args)         throws IOException 
               {
                 BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
                 String str = null;
                 boolean result = true;
                 System.out.println("Enter your String.....");
                 str = br.readLine();
                 str = str.toLowerCase();
                 int asc[]=ascii(str);
                 int len = asc.length;
                 int comp[]=sort(asc,len);
                 if(result==compare(comp))
                 {
                     System.out.println("The Given String is Unique");
                 }
                 else
                {
                        System.out.println("The Given String is not Unique");
                 }
              }

}