Program Java do sprawdzania, czy dwa ciągi są anagramem | Program anagramowy
Opublikowany: 2021-07-23Spis treści
Mniej znane fakty o Javie
Będąc jednym z najtrwalszych języków programowania, Java jest używana na całym świecie ze względu na jego solidne i elastyczne funkcje. Stabilność i wszechstronność Javy sprawiły, że jest to jeden z najbardziej poszukiwanych języków programowania. Istnieje jednak kilka mniej znanych faktów dotyczących tego bezpiecznego języka programowania. Poznajmy kilka z nich.
- Dąb to oryginalna nazwa Javy.
- Ucząc się tego języka programowania można sporo zarobić.
- Java jest drugim najbardziej zaludnionym językiem programowania na świecie, pierwszym z nich jest C.
- Na Javie pracuje około 3 miliardów urządzeń na całym świecie.
- Java to język programowania uwzględniający wielkość liter. tj. „Final” i „final” nie są takie same w kodzie Java. Przeczytaj więcej o tym, dlaczego java jest tak popularna wśród programistów.
Przegląd anagramu
Jeśli łańcuch zostanie przekształcony w inny przez zmianę jego znaków, wtedy mówi się, że dwa łańcuchy są anagramami siebie nawzajem. Jednak liczba znaków w początkowym ciągu i w otrzymanym ciągu powinny być takie same. Aby lepiej zrozumieć pojęcie anagramu, rozważmy dwa ciągi znaków: „bóg” i „pies”.
Ciągi „bóg” i „pies” są anagramami siebie nawzajem, ponieważ pierwszy ciąg można zmienić, aby uzyskać drugi, zamieniając pozycje znaków „d” i „g”. Dla dowolnych dwóch ciągów wejściowych obliczana jest częstotliwość każdego znaku, aby sprawdzić, czy ciągi są anagramami innych, czy nie. Tak więc anagram ciągu można zdefiniować jako dowolny inny ciąg, który ma te same znaki z taką samą częstotliwością, jak ciąg wejściowy w dowolnej sekwencji.
Algorytm dla programu Anagram w Javie
Krok 1: Zdefiniuj dwa ciągi wejściowe.
Krok 2: Określana jest długość każdego ciągu. Ciągi wejściowe nie są anagramami siebie nawzajem, jeśli mają różne długości ciągów.
Krok 3: Jeśli ciągi mają tę samą długość, znaki ciągu są konwertowane na małe litery, aby ułatwić porównanie.
Krok 4: Znaki ciągu są sortowane według wbudowanych funkcji lub konwertowane na tablicę znaków, a następnie sortowane.
Krok 5: Posortowana tablica znaków jest sprawdzana pod kątem równości.
Implementacja programu Anagram w Javie
Istnieje kilka rozwiązań pozwalających na zaimplementowanie kodu w celu sprawdzenia, czy dwa łańcuchy są anagramami, czy nie. Dla każdego rozwiązania omówionego w kolejnych rozdziałach, krok 2 opisanego powyżej algorytmu stanowi podstawę i umożliwia wczesne wyjście w przypadku niezgodności długości ciągów. W kolejnych sekcjach przyjrzyjmy się bliżej różnym typom pisania kodu dla logiki anagramowej.
Podejście do sortowania
Znaki każdego ciągu wejściowego można posortować, aby uzyskać dwie znormalizowane tablice znaków. Jeśli znormalizowane tablice obu ciągów wejściowych są takie same, ciągi są uważane za anagramy siebie nawzajem i odwrotnie.
Zrozumienie i implementacja tego kodu są łatwiejsze. Złożoność czasowa powyższego rozwiązania wynosi O(n log n) i wymagana jest dodatkowa przestrzeń do przechowywania tablic znaków ciągów wejściowych.
Ucz się kursów rozwoju oprogramowania online z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.
Podejście liczenia do implementacji logiki anagram
W tym podejściu mierzona jest liczba istnień każdego znaku w dwóch ciągach wejściowych. Jeśli częstotliwość każdego znaku w obu ciągach jest identyczna, ciągi są anagramami siebie nawzajem.
Zbudujmy pojedynczy histogram, aby zaoszczędzić trochę pamięci. W pierwszym łańcuchu liczniki każdego znaku są zwiększane, podczas gdy liczniki są zmniejszane w przypadku drugiego. Jeśli ostateczny wynik równoważy wszystko do zera, to struny są anagramami.
To rozwiązanie wykonuje się szybciej niż poprzednie rozwiązanie, a jego złożoność czasowa wynosi O(n). Jednak do zliczenia znaków wymagana jest dodatkowa przestrzeń. To rozwiązanie jest praktycznie skuteczne tylko w przypadku stringów o mniejszym zasięgu znaków. Innym faktem dotyczącym tego rozwiązania jest to, że wykorzystuje ograniczoną liczbę wbudowanych funkcji Javy, a tym samym zwiększa długość kodu.
Zamówienie: pomysły i tematy dotyczące projektów Java
Określ anagramy, sprawdzając za pomocą MultiSet
Zastosowanie MultiSetu, kolekcji wspomagającej niezależne od zamówienia porównywanie z identycznymi elementami, upraszcza proces liczenia i porównywania w tym rozwiązaniu.
Każdy ciąg wejściowy jest początkowo konwertowany na MultiSet znaków, a następnie sprawdzany pod kątem parzystości.
Złożoność czasowa tego rozwiązania wynosi O(n). Jest to podobne do podejścia liczenia w celu określenia anagramów. Może jednak działać wydajnie w przypadku ciągów o większej długości. Ponadto kodowanie obejmuje większą liczbę funkcji biblioteki Java.
Podejście oparte na literach w celu określenia anagramów
Wszystkie omówione dotychczas rozwiązania uwzględniają znaki interpunkcyjne również jako część ciągu. Ponadto w tych rozwiązaniach rozróżniana jest wielkość liter. Podejście oparte na literach implementuje kod do sprawdzania ciągów wejściowych na podstawie językowej definicji anagramów. W tym podejściu spacje i znaki interpunkcyjne nie są uważane za część ciągu wejściowego.
Pierwszym krokiem podczas wdrażania rozwiązania opartego na literach jest eliminacja niechcianych znaków i konwersja wszystkich prawidłowych znaków na małe litery. Po tym kroku można użyć dowolnej z omówionych powyżej implementacji do sprawdzenia, czy łańcuchy są anagramami, czy nie.
Jeśli chcesz dowiedzieć się więcej o Java, tworzeniu oprogramowania typu full-stack, sprawdź program Executive PG UpGrad i IIIT-B w tworzeniu oprogramowania – specjalizacja w tworzeniu pełnego stosu, który jest przeznaczony dla pracujących profesjonalistów i oferuje ponad 500 godzin rygorystycznego szkolenia , 9+ projektów i zadań, status absolwentów IIIT-B, praktyczne praktyczne projekty zwieńczenia i pomoc w pracy z najlepszymi firmami.
