Добро пожаловать в раздел Разгадывание математических загадок с помощью JavaScript. JavaScript — один из самых популярных и высокооплачиваемых языков программирования в наши дни. Это также один из самых простых языков программирования для написания кода.
Мы решили опубликовать серию статей о задачах по математике и о том, как их решать с помощью JavaScript.
Прежде чем мы начнем, вот несколько предварительных условий:
- Вы должны быть знакомы с JavaScript, OOJS и ES2015 и выше.
- Вы должны быть знакомы со структурами данных и алгоритмами.
Достаточно сказано! Давайте начнем…
Группирование анаграмм из списка строк
Анаграммы — это строки с одинаковыми символами в разном порядке. Постановка проблемы заключается в том, как сгруппировать анаграммы из заданного списка строк. Например, если у нас есть список строк:
Input: ['God', 'dog', 'cat'] Output: [['God', 'dog'], ['cat']];
Сначала нам нужно решить проблему с анаграммой. Сравните две строки и проанализируйте, являются ли они анаграммами.
function anagrams(str, str2) { str = sortedStr(str); str2 = sortedStr(str2); return str === str2; } function sortedStr(str = '') { const strArr = str.split(''); strArr.sort(); return strArr.join('').toLowerCase(); }
Теперь нам нужно реализовать логику для группировки:
function group(arr = []) { if (arr.length === 0) return; const groups = []; if (groups.length === 0) { groups.push([arr[0]]); } for (const str of arr) { let isGrouped = false; for (const group of groups) { const existing = group.includes(str); isGrouped = existing || !existing && anagrams(group[group.length - 1], str); if (isGrouped && !existing) { group.push(str); } } if (!isGrouped) { groups.push([str]); } } return groups; }
Отлично! Но можем ли мы еще больше сократить эту логику и сделать код более читабельным? Действительно можем.
function group(arr = []) { if (arr.length === 0) return; const groups = []; for (const str of arr) { const anagramList = arr.filter(c => anagrams(str, c)); anagramList.sort(); if (!groups.find( group => { group.sort(); return group.join('') === anagramList.join(''); } )) { groups.push(anagramList); } } return groups; }
Второе решение зависит от ваших знаний библиотеки JavaScript и может быть не самым эффективным решением. Если у вас есть лучшее решение, не стесняйтесь публиковать в разделе комментариев ниже.