1. Обзор
В этом уроке мы увидим, как проверить, содержит ли строка все буквы алфавита или нет.
Вот краткий пример: ” Фермер Джек понял, что большие желтые одеяла стоят дорого. ” – который на самом деле содержит все буквы алфавита.
Мы обсудим три подхода.
Сначала мы смоделируем алгоритм, используя императивный подход. Затем будут использоваться регулярные выражения. И, наконец, мы воспользуемся более декларативным подходом с использованием Java 8.
Кроме того, мы обсудим Большую сложность принятых подходов.
2. Императивный алгоритм
Давайте реализуем императивный алгоритм. Для этого сначала создадим логический массив visited. Затем мы пройдем через входную строку символ за символом и пометим символ как посещенный.
Обратите внимание, что Верхний регистр и Нижний регистр считаются одинаковыми. Таким образом, индекс 0 представляет и А, и а, аналогично, индекс 25 представляет и Z, и z.
Наконец, мы проверим, все ли символы в посещенном массиве имеют значение true:
public class EnglishAlphabetLetters {
public static boolean checkStringForAllTheLetters(String input) {
int index = 0;
boolean[] visited = new boolean[26];
for (int id = 0; id < input.length(); id++) {
if ('a' <= input.charAt(id) && input.charAt(id) <= 'z') {
index = input.charAt(id) - 'a';
} else if ('A' <= input.charAt(id) && input.charAt(id) <= 'Z') {
index = input.charAt(id) - 'A';
}
visited[index] = true;
}
for (int id = 0; id < 26; id++) {
if (!visited[id]) {
return false;
}
}
return true;
}
}Big-O-сложность этой программы равна O(n), где n – длина строки.
Обратите внимание, что существует множество способов оптимизации алгоритма, таких как удаление букв из набора и разрыв, как только Set пуст. Однако для целей упражнения этот алгоритм достаточно хорош.
3. Использование Регулярного Выражения
Используя регулярное выражение, мы можем легко получить те же результаты с помощью нескольких строк кода:
public static boolean checkStringForAllLetterUsingRegex(String input) {
return input.toLowerCase()
.replaceAll("[^a-z]", "")
.replaceAll("(.)(?=.*\\1)", "")
.length() == 26;
}Здесь мы сначала исключаем все символы, кроме букв алфавита, из ввода . Затем мы удаляем дубликаты символов. Наконец, мы считаем буквы и убеждаемся, что у нас есть все, 26.
Несмотря на меньшую производительность, Большая сложность этого подхода также имеет тенденцию к O(n).
4. Поток Java 8
Используя функции Java 8, мы можем легко достичь того же результата более компактным и декларативным способом, используя методы Stream filter и distinct :
public static boolean checkStringForAllLetterUsingStream(String input) {
long c = input.toLowerCase().chars()
.filter(ch -> ch >= 'a' && ch <= 'z')
.distinct()
.count();
return c == 26;
}Большая-O-сложность этого подхода также будет O(n).
4. Тестирование
Давайте проверим счастливый путь для нашего алгоритма:
@Test
public void givenString_whenContainsAllCharacter_thenTrue() {
String sentence = "Farmer jack realized that big yellow quilts were expensive";
assertTrue(EnglishAlphabetLetters.checkStringForAllTheLetters(sentence));
}Здесь предложение содержит все буквы алфавита, следовательно, мы ожидаем true в результате.
5. Заключение
В этом уроке мы рассмотрели, как проверить, содержит ли строка все буквы алфавита .
Сначала мы увидели несколько способов реализовать это с помощью традиционного императивного программирования, регулярных выражений и потоков Java 8.
Полный исходный код доступен на GitHub .