Anagramy

Hooray! Ten artykuł oznacza ostatnie wyzwanie manipulacji ciągami w tej części kursu. Przebyliśmy długą drogę!

W tym wyzwaniu rozważymy dwa sposoby wykrywania anagramów w JavaScript.

Co to jest anagram?

Mówi się, że słowo jest anagramem innego słowa, gdy może być utworzone przez zmianę układu liter innego słowa, używając każdej litery tylko raz. Np. listen jest anagramem silent.

Zajmijmy się pracą, dobrze?

Powinieneś już mieć ustawione środowisko programistyczne dla tego kursu. Zaktualizuj swoje sklonowane repozytorium, wykonując polecenie git pull. Wewnątrz folderu Beginner, przejdź do folderu isAnagram. Nasza praca w tym wyzwaniu będzie wykonywana właśnie tutaj. Upewnij się, że podążasz za nim w pliku theindex-START.js.

Wyzwanie

Dając dwa ciągi znaków, napisz algorytm sprawdzający, czy są one anagramami siebie nawzajem. Zwróć wartość true, jeśli przejdą test i false, jeśli nie. E.g

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

Myślenie algorytmiczne

W rozwiązaniu tego zadania, napiszemy funkcję, która przyjmie dwa parametry, tj. dwa ciągi do porównania.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

Wewnątrz funkcji, porównamy oba słowa, aby zobaczyć, czy zawierają te same znaki użyte tę samą liczbę razy. Aby uniknąć błędów, sanityzujemy ciąg znaków pozbywając się niechcianych znaków i spacji, ponieważ nie są to litery alfabetu.

Wykonujemy również konwersję wszystkich znaków do wspólnej wielkości liter przed wykonaniem jakichkolwiek porównań, aby uniknąć błędów wynikających z różnej kapitalizacji. Sprawdzenie, czy oba słowa mają tę samą długość, jest również bardzo ważne, ponieważ jest to podstawowy czynnik prawidłowego porównania.

Zróbmy to.

Implementacja kodu

Rozważymy teraz dwa sposoby implementacji naszego rozwiązania zgodnie z naszą logiką algorytmiczną powyżej. Są to:

• Porównanie bezpośrednie
• Porównanie mapy znaków

Porównanie bezpośrednie

W tym podejściu definiujemy funkcję, która przyjmuje dwa parametry, tj. dwa ciągi znaków do porównania. Następnie przechodzimy do czyszczenia obu ciągów, aby upewnić się, że porównujemy tylko litery i we wspólnym przypadku.

Czyszczenie ciągu Aby oczyścić ciąg, tworzymy funkcję sanitizeString. Ta funkcja przyjmuje jako parametr łańcuch, który ma zostać oczyszczony, i używa metod .toLowerCase(), .replace(), .split(), .sort() i .join() do manipulowania łańcuchem znaków, jak pokazano poniżej:

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

Porozkładajmy to trochę na czynniki pierwsze:

• Po pierwsze, konwertujemy cały łańcuch na małe litery za pomocą metody .toLowerCase().
• Następnie używamy metody .replace() do przeszukania łańcucha za pomocą określonego wzorca wyrażenia regularnego i zastąpienia każdego znaku niealfabetycznego pustym łańcuchem. To pozostawia nam tylko litery. Żadnych spacji, żadnych symboli!
• Następnie wywołujemy metodę .split(), aby podzielić łańcuch na tablicę znaków.
• Używając metody .sort(), sortujemy litery (elementy) w tablicy w porządku alfabetycznym.
• I w końcu łączymy uporządkowaną alfabetycznie tablicę liter z powrotem, aby ponownie utworzyć łańcuch.

Ten łańcuch jest tym, co zwracamy jako łańcuch oczyszczony.

Gładko!** Prawda?**

Porównanie oczyszczonych łańcuchówOczyszczenie łańcucha w sposób opisany powyżej jest prawdopodobnie najtrudniejszą częścią tego rozwiązania. Następnie po prostu czyścimy otrzymane ciągi za pomocą funkcji sanitizeString i porównujemy wyniki. Jeśli oba łańcuchy pasują do siebie, zwracamy true oznaczające, że przeszły one jako anagramy. Jeśli nie pasują, zwracamy false oznaczające, że nimi nie są.

Zobacz pełne rozwiązanie poniżej:

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

Jeden w dół!** Zróbmy coś jeszcze dziwniejszego! 😈**

Jak zobaczysz, podejście, które teraz rozważymy, podąża za bardziej stopniową procedurą rozwiązywania problemu.

Porównanie mapy znaków

W tym podejściu najpierw generujemy mapę znaków przy użyciu naszej funkcji createCharMap.

Co to jest mapa znaków?

Jak używane w tym kontekście , obiekt mapy znaków jest obiektem, który mapuje każdy znak w łańcuchu do liczby razy, że występuje w ciągu.

Tworzenie mapy znakówW naszej poniższej funkcji createCharMap używamy pętli for…of do iteracji po każdym znaku otrzymanego łańcucha znaków.

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

Dla każdego znaku sprawdzamy, czy znak ten istnieje już jako właściwość w mapie znaków charMap przy użyciu metody .hasOwnProperty(). Jeśli tak, to zwiększamy jego wartość, a jeśli nie, to dodajemy znak jako właściwość i ustawiamy jego wartość na 1.

Na koniec zwracamy charMap, który jest obiektem mapy znaków.

Porównanie map znakówTeraz, gdy mamy już sposób na wygenerowanie map znaków, następnym krokiem będzie porównanie map znaków dla obu łańcuchów, jak pokazano w poniższym rozwiązaniu:

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 }}

Zauważ, że najpierw sprawdzamy, czy długości obu łańcuchów są równe. Jeśli nie są, zwracamy false, ponieważ jest to wskaźnik, że nigdy nie mogą być anagramami. Jeśli jednak są, idziemy dalej, aby wygenerować ich mapy znaków przechowywane jako zmienne stringAMap i stringBMap.

Następnie używamy pętli for…in, aby porównać każdy znak i wartość w stringAMap z odpowiadającą mu wartością w stringBMap. Jeśli jakieś wartości nie pasują, zwracamy false jako wskazówkę, że ciągi nie są anagramami. Jeśli jednak wszystkie wartości pasują, test jest zaliczony i zwracamy true jako wskazówkę, że testowane ciągi rzeczywiście są anagramami.

Udało się. Rzeczywiście, dłuższa implementacja, ale zdecydowanie bardziej wyjaśniająca.

Uruchommy teraz nasze testy, dobrze?

Testowanie poprawności za pomocą Jest

Aby przetestować każde z powyższych rozwiązań, uruchom następujące polecenie z terminala:

npm run test isAnagram

• Porównanie bezpośrednie

• Porównanie mapy znaków

Wygląda na to, że zawsze radzimy sobie świetnie! Przeszliśmy wszystkie testy.

Testowanie wydajności za pomocą JSPerf

Tutaj przeprowadzamy test wydajności, aby określić, które rozwiązanie jest szybsze. Znajdź zrzut ekranu z wynikiem poniżej:

Z wyniku, obserwujemy, że:

Szybszą implementacją jest podejście Character Map Comparison i metoda Direct Comparison choć zwięzła jest około 52% wolniejsza.

**Zaskakujące, prawda? Metryki jednak nigdy nie kłamią!**

Zastosowanie praktyczne

Zbadane powyżej algorytmy mogą być stosowane na różne sposoby. Należą do nich:

• Encryption
• Password Generation
• Trusted Time-stamping
• Coding Interviews
• Generating Mnemonics
• Word games
  

  Conclusion

Rozważając techniki i koncepcje eksplorowane powyżej, poznaliśmy wartościowe sposoby manipulowania ciągami znaków w celu określenia, czy są one anagramami. Zbadaliśmy również różne obszary, w których ta wiedza może być bezpośrednio wykorzystana.

Po przeprowadzeniu naszych testów wydajności możemy teraz stwierdzić, że najbardziej optymalnym podejściem do rozwiązania tego problemu jest metoda porównywania map znaków.

Dalsze czytanie

Aby dowiedzieć się więcej na temat pojęć i technik wyróżnionych powyżej, możesz skorzystać z następujących odnośników:

• Regular Expressions
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• For…of vs for…in loop

Do zobaczenia w następnej serii artykułów poświęconych algorytmom manipulacji tablicami!✌🏿

Podobał Ci się ten artykuł? Śledź @worldclassdev na Twitterze