Определите, является ли список, составленный из элементов анаграммы в Java 8

Question

Я хочу определить, является ли список анаграммой или не использует Java 8.

Пример ввода:

"cat", "cta", "act", "atc", "tac", "tca"

Я написал следующую функцию, которая выполняет эту работу, но мне интересно, есть ли лучший и элегантный способ сделать это.

boolean isAnagram(String[] list) {
    long count = Stream.of(list)
            .map(String::toCharArray)
            .map(arr -> {
                Arrays.sort(arr);
                return arr;
            })
            .map(String::valueOf)
            .distinct()
            .count();
    return count == 1;

}

Кажется, я не могу отсортировать массив символов с помощью метода Stream.sorted(), поэтому я использовал второй оператор карты. Если есть какой-то способ, которым я могу работать непосредственно с потоком символов вместо массива потока символов, это также поможет.

Answer 1

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

Поэтому, когда мы создаем метод для преобразования String в канонический ключ (т.е. все отсортированные символы)

private CharBuffer canonical(String s) {
    char[] array = s.toCharArray();
    Arrays.sort(array);
    return CharBuffer.wrap(array);
}

мы можем просто проверить, все ли последующие элементы равны первому:

boolean isAnagram(String[] list) {
    if(list.length == 0) return false;
    return Arrays.stream(list, 1, list.length)
        .map(this::canonical)
        .allMatch(canonical(list[0])::equals);
}

Обратите внимание, что для ссылок на методы вида expression::name выражение оценивается один раз, а результат захватывается, поэтому canonical(list[0]) оценивается только один раз для всей операции потока и только equals вызывается для каждого элемента.

Конечно, вы также можете использовать Stream API для создания канонических ключей:

private IntBuffer canonical(String s) {
    return IntBuffer.wrap(s.chars().sorted().toArray());
}

^{(метод isAnagram не требует изменений)}

Обратите внимание, что CharBuffer и IntBuffer могут использоваться в качестве облегченных оболочек для массивов, как в этом ответе, и реализовывать equals и hashCode соответственно, исходя из фактического содержимого массива.

Answer 2

Альтернативно, обновленная версия вашей реализации, которая могла бы работать, была бы:

boolean isAnagram(String[] list) {
    return Stream.of(list) // Stream<String>
            .map(String::toCharArray) // Stream<char[]>
            .peek(Arrays::sort) // sort 
            .map(String::valueOf) // Stream<String>
            .distinct() //distinct
            .count() == 1;
}

Answer 3

Я бы не сортировал массив символов, так как сортировка O(NlogN), что здесь не нужно.

Все, что нам нужно, это для каждого слова списка подсчитывать вхождения каждого символа. Для этого мы собираем символы каждого слова в Map<Integer, Long>, причем ключи - это каждый символ, а значение - его количество.

Затем мы проверяем, что для всех слов в аргументе массива у нас одинаковое количество символов, то есть одна и та же карта:

return Arrays.stream(list)
    .map(word -> word.chars()
            .boxed().collect(Collectors.grouping(c -> c, Collectors.counting()))
    .distinct()
    .count() == 1;

Answer 4

Или может быть с BitSet:

  System.out.println(stream.map(String::chars)
        .map(x -> {
            BitSet bitSet = new BitSet();
            x.forEach(bitSet::set);
            return bitSet;
        })
        .collect(Collector.of(
            BitSet::new,
            BitSet::xor,
            (left, right) -> {
                left.xor(right);
                return left;
            }
        ))
        .cardinality() == 0);

Answer 5

Вместо создания и сортировки char[] или int[], что не может быть выполнено внутри строки и, таким образом, «разбивает» поток, вы можете получить Stream из chars в строках и отсортировать их до преобразование их в массивы. Обратите внимание, что это IntSteam, и String.valueOf(int[]) будет включать адрес памяти массива, что здесь не очень полезно, поэтому лучше использовать Arrays.toString в этом случае.

boolean anagrams = Stream.of(words)
        .map(String::chars).map(IntStream::sorted)
        .map(IntStream::toArray).map(Arrays::toString)
        .distinct().count() == 1;

Конечно, вы также можете использовать map(s -> Arrays.toString(s.chars().sorted().toArray())) вместо серии из четырех maps. Не уверен, что есть (значительная) разница в скорости, скорее всего, это дело вкуса.

Кроме того, вы можете использовать IntBuffer.wrap для сопоставления массивов, что должно быть значительно быстрее, чем Arrays.toString (благодаря Хольгеру в комментариях).

boolean anagrams = Stream.of(words)
        .map(s -> IntBuffer.wrap(s.chars().sorted().toArray()))
        .distinct().count() == 1;