Эффективные конструкции языка Java для проверки того, является ли строка панграммой?

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

Я ищу гораздо более элегантный способ проверить строку панграммы в java.

Элегантные, как минимум строки кода, приветствуются и другие эффективные алгоритмы.

Предоставьте предложения без лямбда-выражений.

    private static boolean isPangrams(String ip) {

        char[] characterArray = ip.toLowerCase().toCharArray();
        int map[] = new int[26];
        int sum = 0;

        for(char current : characterArray) {

            int asciiCode = (int) current;
            if (asciiCode >= 97 && asciiCode <= 122) {

                if (map[122 - asciiCode] == 0) {

                    sum += 1;
                    map[122 - asciiCode] = 1;
                }
            }
        }

        return sum == 26;
    }

java optimization performance algorithm pangram
person alkber    schedule 17.06.2016    source источник
comment
Что ж, улучшать рабочий код следует на codereview.stackexchange.com... в любом случае: лучше не становится, но вы можете использовать Bitset вместо массива int - зачем использовать числа, когда true/false - это то, что вам действительно нужно необходимость?!   -  person GhostCat    schedule 17.06.2016
comment
BitSet был аккуратным вводом. Спасибо.   -  person alkber    schedule 17.06.2016

Ответы (5)


arrow_upward
3
arrow_downward

Для этого вы можете использовать побитовые операции:

private static boolean isPangrams(String ip) {
    int flags = 0;
    for(char current : ip.toLowerCase().toCharArray()) {
        if (current >= 'a' && current <= 'z') {
            flags |= 0x01<<(current-'a');
        }
    }
    return flags == 0x3ffffff;
}

jDoodle

Код работает следующим образом: мы рассматриваем int как 32-битное число. Каждый бит до 26 является флагом (так сказать, boolean). Изначально все флаги равны false, потому что мы инициализируем flags значением 0.

Теперь мы перебираем символы строки. В случае, если символ является строчной буквой, мы устанавливаем флаг соответствующего флага в true (независимо от того, был ли он установлен в true ранее).

Наконец, мы проверяем, установлены ли все младшие 26 битов в true. Если да, то flags равно 0x3ffffff (это шестнадцатеричное число, равное двоичному 1111111111111111111111. Если это так, мы возвращаем true. В противном случае мы возвращаем false.

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

person Willem Van Onsem    schedule 17.06.2016
comment
Зачем приводить char 'current' и сохранять его в int 'asciiCode'? Все операции, которые вы делаете, могут выполняться с исходным char 'current' вместо 'asciiCode'. - person MrSmith42; 17.06.2016

arrow_upward
4
arrow_downward

Если вам нужен трудный для понимания ответ на несколько строк:

private static boolean isPangrams(String ip) {
  return 26== (new HashSet(Arrays.asList(ip.toUpperCase().replaceAll("[^A-Z]", "").toCharArray()))).size();
}

Пояснение:

  1. сделать строку в верхнем регистре (чтобы обрабатывать «a» и «A» одинаково)
  2. удалить все символы кроме A, B...Z
  3. преобразовать его в char[]
  4. преобразовать массив в Collection
  5. добавьте коллекцию в Set, чтобы избавиться от всех дублетов
  6. проверить размер набора.

Вы должны понимать, что этот код неудобен для чтения и неэффективен.

person MrSmith42    schedule 17.06.2016
comment
Да, это терпит неудачу для производительной части. Тем не менее, соответствует моему требованию. - person alkber; 17.06.2016

arrow_upward
2
arrow_downward

Вы можете «упаковать» данные, если строка содержит заданную букву внутри переменной int.

static boolean pangram (String s) {
    int check = 0;
    String lowerCase = s.toLowerCase();
    for (int i = 0; i < lowerCase.length(); i++) {
      char ch = lowerCase.charAt(i);
      if (ch >= 'a' && ch <= 'z') {
        check |= (1 << s.charAt(i) - 'a');
      }
    }
    return check == 67108863;
  }

Магическое число в конце 0b00000011111111111111111111111111

person cliffroot    schedule 17.06.2016

arrow_upward
0
arrow_downward

Наиболее эффективное решение временной сложности O(n):

  1. Переберите строку и поместите каждую букву в HashMap (key: letter, value: count)
  2. Перебирайте карту и проверяйте каждую букву алфавита.
person Dmitry Volokh    schedule 17.06.2016
comment
Алгоритм в вопросе тоже O(n). Таким образом, никакое улучшение сложности невозможно. - person MrSmith42; 17.06.2016

arrow_upward
0
arrow_downward

Вы можете остановить весь метод с помощью инструкции return false, если обнаружите, что map[122 - asciiCode] не равна нулю, потому что с тех пор это больше не панграмма, и вы избавляетесь от остальной части for() - я прав? Я знаю, что это не то улучшение, которое вы ожидаете (особенно с 26 шагами), а просто то, что пришло мне в голову.

        if (map[122 - asciiCode] == 0) {

            sum += 1;
            map[122 - asciiCode] = 1;
        } else return false;
person Daddelbob    schedule 17.06.2016
comment
Я думал, что панграмма определяется как все символы (a-z) по крайней мере один раз. - person jensgram; 17.06.2016
comment
Вы правы, в панграмме должен быть каждый символ хотя бы один раз. Я придумал идеальную панграмму, в которой каждая буква содержится только один раз. Wikipedia/Pangram: Идеальная панграмма содержит каждую букву алфавита только один раз и может считаться анаграммой алфавита. - person Daddelbob; 22.06.2016