На этой неделе я работал над другой проблемой алгоритма из моего Курса Удеми Кольта Стила. Это еще одна проблема типа частотомера, но на этот раз я работаю над тем, чтобы проверить, являются ли две строки анаграммами друг друга.
Частотомер - действительный
Учитывая две строки, напишите функцию, чтобы определить, является ли вторая строка анаграммой первой. Анаграмма - это слово, фраза или имя, образованное перестановкой букв другого, например «кино», образованное от «айсман».
Пример
Входные данные: строка1 = «», строка2 = «»
Выход: истина
Входные данные: string1 = «aaz», string2 = «zza»
Выходные данные: false
Входные данные: строка1 = «анаграмма», строка2 = «нагарам»
Выход: истина
Входные данные: строка1 = «классно», строка2 = «потрясающе»
Выходные данные: ложь
Ограничения
- Все входные данные - отдельные слова
- Все входные данные в нижнем регистре
- Ни в одном из полей ввода нет пробелов, знаков препинания или цифр.
function validAnagram(string1, string2){
}
Мой процесс
Понимание проблемы
Прежде чем приступить к программированию, давайте еще раз сформулируем проблему. Мне нужно создать функцию, которая сообщит мне, являются ли два моих строковых входа строка1 и строка2 анаграммами друг друга. Если это анаграммы, моя функция должна возвращать true, если они не анаграммы, моя функция должна возвращать false. Мои строки будут состоять из отдельных слов без пробелов, цифр, знаков препинания и в нижнем регистре.
Разрушая это
Пришло время прокомментировать, что мне нужно сделать для решения этой проблемы.
function validAnagram(string1, string2){
// Do something...
/* return true if string1 and string2 are anagrams, return false otherwise */
}
Мой первый план действий в разделе «Сделайте что-нибудь…» - проверить, были ли две строки одинаковой длины; если бы они не были одинаковой, я бы автоматически вернул false. Затем необходимо создать объект, который имеет ключи букв string1 со значениями количества раз, которое они встречаются в этом слове. А затем заставить другой объект делать то же самое, но с строкой2.
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
}
// 1. Create empty objects
let stringFreq1 = {}
let stringFreq2 = {}
// 2. Loop through string1 and then string2 to add to the objects
/* return true if string1 and string2 are anagrams, return false otherwise */
}
Я хочу, чтобы мои объекты выглядели так.
EXAMPLE
inputs: validAnagram('anagram', 'nagaram')
stringFreq1 = {'a':3, 'n':1, 'g':1, 'r':1, 'm': 1}
stringFreq2 = {'n':1, 'a':3, 'g':1, 'r':1, 'm': 1}
Так что на этот раз я буду использовать цикл for… of для перебора моих двух строк. Если буква в строке уже является ключом объекта, я добавлю 1 к значению. Если нет, то я установлю его на 0 и добавлю 1. Затем я собираюсь сравнить ключи и значения обоих объектов друг с другом.
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
}
// 1. Create empty objects
let stringFreq1 = {}
let stringFreq2 = {}
// 2. Loop through string1 and then string2 to add to the objects
for (let letter of string1){
stringFreq1[letter] = (stringFreq1[letter] || 0) + 1
}
for (let letter of string2){
stringFreq2[letter] = (stringFreq2[letter] || 0) + 1
}
// 3. Compare the keys and values in both objects
/* return true if string1 and string2 are anagrams, return false otherwise */
}
Теперь, когда мои объекты созданы, я сравню значения ключей в обоих объектах, чтобы увидеть, не совпадают ли они с одинаковыми ключами, и если да, то он немедленно вернет false. Затем, если они не имеют одинаковых значений для этих ключей, если да, он немедленно вернет false. Если он не вернет false ни для одного из этих тестов, он вернет true, и обе строки являются истинными анаграммами друг друга.
Я буду использовать for… in для обхода моих объектов
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
}
// 1. Create empty objects
let stringFreq1 = {}
let stringFreq2 = {}
// 2. Loop through string1 and then string2 to add to the objects
for (let letter of string1){
stringFreq1[letter] = (stringFreq1[letter] || 0) + 1
}
for (let letter of string2){
stringFreq2[letter] = (stringFreq2[letter] || 0) + 1
}
// 3. Compare the keys and values in both objects
for (let key in stringFreq1){
// 3a. checking if the keys of stringFreq1 are missing from stringFreq2
if(!(key in stringFreq2)){
return false
}
// 3b. checking if the key's value of stringFreq1 is different from the key's value in stringFreq2
if (stringFreq2[key] !== stringFreq1[key]){
return false
}
}
/* return true if string1 and string2 are anagrams, return false otherwise */
return true
}
Решено
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
}
let stringFreq1 = {}
let stringFreq2 = {}
for (let letter of string1){
stringFreq1[letter] = (stringFreq1[letter] || 0) + 1
}
for (let letter of string2){
stringFreq2[letter] = (stringFreq2[letter] || 0) + 1
}
for (let key in stringFreq1){
if(!(key in stringFreq2)){
return false
}
if (stringFreq2[key] !== stringFreq1[key]){
return false
}
}
return true
}
Мои мысли
Это была довольно простая проблема, которая помогла мне усилить работу с объектами, чтобы избежать вложенных циклов с проблемами, касающимися частоты чего-либо. Эта функция имеет обозначение O (n), что довольно прилично.
