Love Frontend
Сообщество
фронтенд разработчиков
EN

Решения задачи на поиск изограмм.

Дата публикации: 05.07.2019

Изограммы это слова, в которых нет повторяющихся букв. Эту задачу можно услышать на некоторых собеседованиях. Задаётся рядом или вместо задачи найти палиндром или уникальную букву в строке и так далее. Для тех, кто хочет сначала сам потренировать свой мозг, вот ссылка на задачу.

По условиям задачи мы должны написать функцию, которая принимает слово и возвращает true если в слове нет повторяющихся букв и false если есть дублирующиеся символы, при чём регистронезависимы. Примеры работы функции:

isIsogram('Dermatoglyphics') == true
isIsogram('aba') == false
isIsogram('moOse') == false // игнорируем caps

Один из самых распространённых методов решения это конечно использование регулярных выражений:

function isIsogram(str) {
return !/(\w).*\1/i.test(str)
}

Регулярное выражение можно также написать разными способами, но смысл в основном один и тот же. Мы ищем любую букву (напомним, что мета символ \w в регулярках, это по сути класс [ A-Z a-z 0-9_ ]. Круглые скобки вокруг символа нужны для его группировки, и потом с помощью порядкового номера можно использовать найденное выражение в этой же регулярке. То есть в данном случае мы обращаемся к нему по номеру 1 в конце. . (точка) — означает любой символ. Звёздочка * означает любое количество символов и также отсутствие этих символов. А затем мы вновь берём встретившийся ранее символ (мы обращаемся к нему по цифре \1, благодаря тому что сгруппировали его, то есть взяли в круглые скобки, если бы была ещё одна группа, то к ней можно было бы обратиться цифрой \2). Таким образом, мы можем с помощью регулярного выражения определить есть ли на любой удалённости друг от друга один и тот же символ. И не забываем ставить флаг i, что позволит нам сравнивать символы не зависимо от регистра. Тестируем регулярку на вхождение в строке с помощью метода test. И если такого совпадения нет, то возвращаем true. Значит наше слово не имеет повторяющихся букв. Можно использовать match у метода строки, тогда нужно будет поменять строку и регулярку местами. Лично я после этой задачи решил поглубже изучить регулярные выражения и перечитал по ним книгу.

function isIsogram(str) {
return !str.match(/([a-z]).*\1/i)
}

Но есть ещё очень интересное решение, которое доступно для реализации не на всех языках программирования. Если абстрагироваться от букв и посмотреть на задачу проще, то на самом деле мы поймём, что нам просто нужно найти дубликаты в массиве. Если думать в этом ключе, то можно прийти к этому интересному решению без использования регулярных выражений. Дело в том, что дубли можно убрать с помощью специального объекта Set, особенность которого заключается как раз в том, чтобы хранить не дублирующиеся значения. Если мы вызовем его как конструктор, то он отбросит все дублирующиеся свойства объекта или примитивные значения (например символы в строке) и решение в данном случае будет выглядеть так:

function isIsogram(str) {
return str.length === new Set(str.toLowerCase()).size

Вызов new Set() возвращает строку без дублированных символов, но обратите внимание, чтобы символы сравнивались без учёта регистра, нужно привести их к одному регистру, либо .toLowerCase(), либо .toUpperCase(). Далее у вернувшейся строки нам нужно найти её длину и сравнить с длиной исходной строки. У объекта Set длина (вернее размер объекта) лежит в свойстве size. Теперь понятно, если set сработал и вернул строку с той же длинной, то значит дубликатов не было и исходная строка и строка без дублирования символов должны быть одинаковой длины. Если это не так, значит слово не изограмма и возвращается false. На мой взгляд это самый оригинальный и интересный метод решения данной задачи. но также помните, что эту задачу можно решить совсем топорно с помощью циклов.

function isIsogram(str) {
const letters = {}
if (str == str.toUpperCase()) return true
for (let i = 0; i < str.length; i++) {
if (i > 0 && str[i] == str[i].toUpperCase()) return false
if (str[i] in letters) return false
else letters[str[i]] = 1
}
return true

Оставьте свой e-mail чтобы получать уведомления о свежих статьях.