Anagramy

Horay! Tento článek je posledním úkolem pro manipulaci s řetězci v této části kurzu. Ušli jsme dlouhou cestu!

V této výzvě se budeme zabývat dvěma způsoby, jak v jazyce JavaScript odhalit anagramy.

Co je to anagram?“

O slově se říká, že je anagramem jiného slova, když ho lze vytvořit přeskupením písmen jiného slova s použitím každého písmene právě jednou. Např. listen je anagramem slova silent.

Pustíme se do toho?

Pro tento kurz byste již měli mít nastavené vývojové prostředí. Klonovaný repozitář aktualizujte příkazem git pull. Uvnitř složky Beginner přejděte do složky isAnagram. Zde bude probíhat naše práce pro tento úkol. Ujistěte se, že postupujete podle souboruindex-START.js.

Úkol

Podle dvou řetězců napište algoritmus, který ověří, zda jsou navzájem anagramy. Vraťte true, pokud testem projdou, a false, pokud ne. Např

isAnagram('silent', 'listen') // should return true

Algoritmické myšlení

Při řešení této úlohy napíšeme funkci, která přijme dva parametry, tj. dva řetězce, které se mají porovnat.

BeginnerTailwind.com Naučte se Tailwind CSS od nuly

V rámci funkce porovnáme obě slova, zda obsahují stejný počet použitých znaků. Abychom se vyhnuli chybám, řetězec sanitizujeme, čímž se zbavíme nežádoucích znaků a mezer, protože se nejedná o písmena abecedy.

Před provedením porovnání také převedeme všechny znaky na běžná velká písmena, abychom se vyhnuli chybám způsobeným rozdílným psaním velkých písmen. Velmi důležitá je také kontrola, zda jsou obě slova stejně dlouhá, protože to je primární faktor pro správné porovnání.

Provedeme to.

Implementace kódu

Nyní se budeme zabývat dvěma způsoby implementace našeho řešení podle naší výše uvedené algoritmické logiky. Jsou to:

• Přímé porovnání
• Porovnání pomocí mapy znaků

Přímé porovnání

V tomto přístupu definujeme funkci, která přijímá dva parametry, tj. dva řetězce, které chceme porovnat. Poté přistoupíme k vyčištění obou řetězců, abychom zajistili, že porovnáváme pouze písmena a ve společném pádu.

Vyčištění řetězcePro vyčištění řetězce vytvoříme funkci sanitizeString. Tato funkce přijme jako parametr řetězec, který má být vyčištěn, a k manipulaci s řetězcem použije metody .toLowerCase(), .replace(), .split(), .sort() a .join(), jak je uvedeno níže:

const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join('');}

Nechme si to trochu rozdělit:

• Nejprve převedeme celý řetězec na malá písmena pomocí metody .toLowerCase().
• Poté pomocí metody .replace() prohledáme řetězec pomocí zadaného vzoru regulárního výrazu a nahradíme každý neabecední znak prázdným řetězcem. Tím nám zůstanou pouze písmena. Žádné mezery, žádné symboly!
• Následující volání .split() rozdělí řetězec na pole znaků.
• Pomocí metody .sort() seřadíme písmena (prvky) v poli podle abecedy.
• A nakonec nyní abecedně seřazené pole písmen opět spojíme dohromady a vytvoříme řetězec.

Tento řetězec vrátíme jako sanitizovaný řetězec.

Hladce!“** Že? „**

Porovnání sanitizovaných řetězcůSanitizace řetězce, jak byla provedena výše, je asi nejsložitější částí tohoto řešení. Dále jednoduše vyčistíme přijaté řetězce pomocí funkce sanitizeString a porovnáme výsledky. Pokud se oba řetězce shodují, vrátíme true, což znamená, že procházejí jako anagramy. Pokud se neshodují, vrátíme false značící, že nejsou.

Podívejte se na kompletní řešení níže:

function isAnagram(stringA, stringB) { const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join(''); } return sanitizeString(stringA) == sanitizeString(stringB)}

Jedna dolů** Pojďme na to divněji! 😈**

Jak uvidíte, přístup, kterým se nyní budeme zabývat, sleduje postup řešení problému více po krocích.

Porovnání mapy znaků

V tomto přístupu nejprve vytvoříme mapu znaků pomocí naší funkce createCharMap.

Co je to mapa znaků

Jak se používá v tomto kontextu , objekt mapy znaků je objekt, který mapuje každý znak v řetězci na počet výskytů v řetězci.

Vytvoření mapy znakůV naší createCharMap funkci níže použijeme cyklus for…of k iteraci každého znaku přijatého řetězce.

function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap}

Pro každý znak zkontrolujeme, zda tento znak již existuje jako vlastnost v mapě znaků charMap pomocí metody .hasOwnProperty(). Pokud ano, zvýšíme jeho hodnotu, a pokud ne, přidáme znak jako vlastnost a nastavíme jeho hodnotu na 1.

Nakonec vrátíme charMap, což je objekt mapy znaků.

Porovnání map znakůTeď, když máme způsob generování map znaků, bude dalším krokem porovnání map znaků pro oba řetězce, jak ukazuje kompletní řešení níže:

function isAnagram(stringA, stringB) { function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap } if (stringA.length === stringB.length) { let stringAMap = createCharMap(stringA) let stringBMap = createCharMap(stringB) for (let char in stringAMap) { if (stringAMap !== stringBMap) { return false } } return true } else { return false }}

Všimněte si, že nejprve kontrolujeme, zda je délka obou řetězců stejná. Pokud nejsou, vrátíme false, protože to je indikátor, že nikdy nemohou být anagramy. Pokud však jsou, pokračujeme dále a vygenerujeme jejich mapy znaků uložené jako proměnné stringAMap a stringBMap.

Dále použijeme cyklus for…in k porovnání každého znaku a hodnoty v stringAMap s odpovídající hodnotou znaku v stringBMap. Pokud se některé hodnoty neshodují, vrátíme false jako informaci, že řetězce nejsou anagramy. Pokud se však všechny hodnoty shodují, testem projdeme a vrátíme true jako informaci, že testované řetězce jsou skutečně anagramy.

Povedlo se. Vskutku delší implementace, ale rozhodně je vysvětlující.

Pustíme teď naše testy, ano?

Testování správnosti pomocí Jestu

Pro otestování každého z výše uvedených řešení spusťte z terminálu následující příkaz:

npm run test isAnagram

• Přímé porovnání

• Porovnání mapy znaků

Zdá se, že nám to vždycky jde skvěle! Prošli jsme všemi testy.

Testování výkonu pomocí JSPerf

Tady provedeme test výkonu, abychom zjistili, které řešení je rychlejší. Níže najdete snímek obrazovky s výsledkem:

Z výsledku pozorujeme, že:

Rychlejší je implementace přístupu Porovnávání map znaků a metoda Přímé porovnávání, i když je stručná, je přibližně o 52 % pomalejší.

**Překvapivé, že? Metriky však nikdy nelžou!**

Praktické využití

Výše zkoumané algoritmy lze použít různými způsoby. Mezi ně patří např:

• Šifrování
• Generování hesel
• Důvěryhodné časové razítko
• Kódování rozhovorů
• Generování mnemotechnik
• Slovní hry
  

  Závěr

Při zvažování výše zkoumaných technik a konceptů, jsme se naučili cenné způsoby manipulace s řetězci za účelem zjištění, zda se jedná o anagramy. Prozkoumali jsme také různé oblasti, ve kterých lze tyto znalosti přímo využít.

Po provedení našich výkonnostních testů můžeme nyní konstatovat, že nejoptimálnějším přístupem k řešení tohoto problému je metoda porovnávání map znaků.

Další literatura

Chcete-li se dozvědět více o výše zdůrazněných konceptech a technikách, můžete použít následující odkazy:

• Regulární výrazy
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• For…of vs for…in cyklus

Uvidíme se v další sadě článků zaměřených na algoritmy manipulace s poli!✌🏿

Líbí se vám tento článek? Sledujte @worldclassdev na Twitteru