Program Java do sprawdzania, czy ciąg jest palindromem

Niektóre problemy w programowaniu mają status klasycznych. Zazwyczaj takie zadania są związane z matematyką i bardzo chętnie zadają je studentom kierunków informatycznych, a także osobom poszukującym pracy na rozmowach kwalifikacyjnych. Są dobre, ponieważ pomagają dość dobrze ustawić myślenie w sposób programistyczny, a także go szkolić. Jednym z takich problemów jest sprawdzenie, czy ciąg znaków jest palindromem i tym zajmiemy się w tym artykule.

Co to jest palindrom i dlaczego można go szukać

Palindrom to liczba, kombinacja liter, słowo lub tekst, który czyta się tak samo w obu kierunkach. Podsumowując, palindrom można nazwać dowolnym zestawem znaków, który jest symetryczny względem środka. Słowo pochodzi od greckich korzeni, które dosłownie wywodzą się z „biegania z powrotem” (palin to „znowu, z powrotem”, a dromos, „bieg”). Palindrom w Javie oznacza to samo, co w ogólnym znaczeniu. Przykłady palindromów:

• 1881
• aaqquqqaa
• Muzyka pop
• Południe
• poziom
• Rewolwer
• Moja siłownia
• Pani, jestem Adam
• A teraz, proszę pana, wojna jest wygrana!

1881 to liczba palindromowa, a pozostałe to łańcuchy palindromów. W tym artykule przyjrzymy się palindromom, które są reprezentowane jako ciągi znaków, ale niektóre algorytmy można całkiem zastosować do innych rodzajów palindromów w Javie. Dlaczego warto szukać palindromów? W rzeczywistości nie często musimy szukać palindromów w życiu codziennym. To dość specyficzne zadanie. Jeśli przypomnimy sobie algorytmy łańcuchowe, w praktyce częściej programiści mogą znaleźć szukanie podłańcucha w łańcuchu, a nie szukanie palindromów lub ich liczby. Jednak problemy związane z palindromami mają ważne zastosowania. Pierwszym z nich jest programowanie olimpiady. Mogą istnieć zadania identyfikacji palindromów. Drugim zastosowaniem, które jest istotne dla początkujących programistów, jest rozmowa kwalifikacyjna. W rozmowie technicznej równie dobrze możesz zostać poproszony o szybkie napisanie programu sprawdzającego, czy łańcuch jest palindromem, może nawet na kartce papieru. Cóż, w nauce najbardziej praktycznym zastosowaniem znajdowania palindromów są algorytmy biologiczne. Według Wikipedii palindromowość związków biologicznych odgrywa ważną rolę we właściwościach różnych związków biologicznych.

Przykład kodu algorytmu palindromu

Pomyślmy. Łańcuch to sekwencja znaków, można powiedzieć, tablica znaków. Najbardziej logiczne byłoby prześledzenie tej sekwencji z obu stron do środka i porównanie skrajnych postaci. Jeśli do momentu dotarcia do środka wszystkie nasze znaki będą pasować, to mamy palindrom. Stwórzmy metodę logiczną validPalindrome(String s), aby sprawdzić, czy String jest palindromem. Kod Javy jest tutaj:

public class PalindromeTest1 {

//method to check if a string is palindrome
public static boolean validPalindrome(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           if (s.charAt(i) != s.charAt(j)) {
               return false;
           }
       }
       return true;
   }

   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!"
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

W głównej metodzie sprawdzamy ciągi palindromiczne „poziom”, „fajny”, „Pani” i „Teraz, proszę pana, wojna jest wygrana!”. Jak widać, pierwszy, trzeci i czwarty to palindromy, ale drugi już nie. Co da program? Więc pierwszy jest palindromem, drugi nie. Ale co jest nie tak z trzecim i czwartym? Dlaczego wynik jest fałszywy ? Prawdopodobnie już zgadłeś, że chodzi o to, że niektóre znaki w tym łańcuchu są wielkie, a inne małe, a dla Javy M i m to dwa różne znaki. Poprawmy program, aby uwzględniał tę różnicę. Oto program do sprawdzania, czy łańcuch jest palindromem, który rozwiązuje problemy z dużymi i małymi literami.

public class PalindromeTest2 {

   //lowercase and uppercase characters should be treated the same:
   public static boolean validPalindrome(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
               return false;
       }
       return true;
   }

   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
        String s4 = "Now, sir, a war is won!"
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

Tym razem wynik jest dla nas bardziej przewidywalny: Cóż… niezupełnie przewidywalne. Sytuacja z „Madame” jest coraz lepsza, ale co z naszym długim i szczęśliwym palindromem „Teraz, proszę pana, wojna jest wygrana!”. To całkiem proste, jeśli pamiętasz, że wszystkie spacje i znaki interpunkcyjne są takie same jak litery w Javie. Musimy więc ponownie ulepszyć nasz algorytm, aby naprawić to niedopatrzenie. Nauczmy nasz program ignorowania spacji i znaków interpunkcyjnych. Mówiąc najprościej, ignorujemy wszystkie znaki niealfanumeryczne. Oto ulepszony program palindromowy w Javie.

public class PalindromeTest3 {

   //in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
   private static boolean isAlphanumeric(char c) {
       return Character.isAlphabetic(c) || Character.isDigit(c);
   }

   public static boolean validPalindromeIgnorePunctuation(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           // skip chars we should ignore
           while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
           while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
           // overskipped -> nothing left to validate
           if (i >= j) return true;

           if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
               return false;
       }
       return true;
   }


   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!";
       boolean b1 = validPalindromeIgnorePunctuation(s1);
       boolean b2 = validPalindromeIgnorePunctuation(s2);
       boolean b3 = validPalindromeIgnorePunctuation(s3);
       boolean b4 = validPalindromeIgnorePunctuation(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

Przynajmniej wynik jest taki, jakiego się po nim spodziewaliśmy: Być może, jeśli dopiero zaczynasz programować, trudno ci zrozumieć, jak działają algorytmy przechodzenia i porównywania łańcuchów. Oczywiście lepiej sobie z tym poradzić, ale można napisać uproszczoną wersję samego przejścia przez tablicę znaków, która w rzeczywistości jest ciągiem znaków. Możesz użyć metody StringBuffer.reverse, aby sprawdzić, czy łańcuch jest palindromem. Zróbmy najprostszą wersję bez sprawdzania symboli niealfanumerycznych oraz wielkich i małych liter.

public class PalindromeTest5 {

   public static boolean validPalindrome(String s) {

       StringBuffer buffer = new StringBuffer(s);
       buffer.reverse();
       String data = buffer.toString();

       if (s.equals(data)) {
           return true;
       }
       return false;
   }
   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!";
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }
}

Wynik jest taki sam jak w pierwszym przykładzie Jeśli chcesz, możesz ulepszyć ten program, tak jak to zrobiliśmy z pierwszym przykładem. Aby utrwalić to, czego się nauczyłeś, zalecamy obejrzenie lekcji wideo z naszego kursu języka Java