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

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

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

Мне нравится идея 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;
}

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

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

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

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

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

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

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

Как насчет использования int для хранения битов, соответствующих индексу буквы алфавита? Или может быть long, чтобы иметь возможность достичь 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;

Это должно быть < O(n) в среднем случае, O(n) в худшем. Но я не уверен, насколько производительны побитовые операции в Java...

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

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

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

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

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

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