Java-programma om te controleren of een string een palindroom is

Sommige problemen bij het programmeren hebben de status van klassieke problemen. Meestal zijn dergelijke taken gerelateerd aan wiskunde en ze vragen graag studenten van computerwetenschappelijke specialiteiten, evenals werkzoekenden tijdens sollicitatiegesprekken. Ze zijn goed omdat ze je helpen om je denken op een programmeerbare manier vrij goed op te zetten, en het ook te trainen. Een van die problemen is het controleren of een string een palindroom is, en dat gaan we in dit artikel bekijken.

Wat is een palindroom en waarom kan je ernaar zoeken?

Een palindroom is een getal, lettercombinatie, woord of tekst die in beide richtingen hetzelfde leest. Samenvattend kan een palindroom elke reeks karakters worden genoemd die symmetrisch is rond het midden ervan. Het woord komt van Griekse wortels die letterlijk zijn afgeleid van "terugrennen" (palin is "opnieuw, terug" en dromos, "rennen"). Palindroom in Java betekent hetzelfde als in algemene betekenis. Voorbeelden van palindromen:

• 1881
• aaqquqqaa
• knal
• Middag
• niveau
• Rotator
• Mijn gym
• Mevrouw, ik ben Adam
• Nu, mijnheer, een oorlog is gewonnen!

1881 is een palindroomnummer en de andere zijn palindroomreeksen. In dit artikel kijken we naar palindromen die worden weergegeven als strings, maar sommige algoritmen zijn goed toepasbaar op andere soorten palindromen in Java. Waarom zou je naar palindromen willen zoeken? In feite hoeven we in het dagelijks leven niet vaak naar palindromen te zoeken. Het is nogal een heel specifieke taak. Als we ons stringalgoritmen herinneren, kunnen programmeurs in de praktijk vaker zoeken naar een substring in een string, en niet zoeken naar palindromen of hun nummer. Problemen in verband met palindromen hebben echter belangrijke toepassingen. De eerste is olympiadeprogrammering. Er kunnen taken zijn om palindromen te identificeren. De tweede toepassing die relevant is voor beginnende programmeurs is interviewen. Tijdens een technisch gesprek je wordt misschien gevraagd om snel een programma te schrijven om te controleren of een string palindroom is, misschien zelfs op een stuk papier. Welnu, in de wetenschap zijn biologische algoritmen de meest praktische toepassing van het vinden van palindromen. Volgens Wikipedia speelt de palindromiciteit van biologische verbindingen een belangrijke rol in de eigenschappen van verschillende biologische verbindingen.

Voorbeeld van algoritmecode voor palindroom

Laten we nadenken. Een string is een opeenvolging van karakters, zou je kunnen zeggen, een reeks tekens. Het zou het meest logisch zijn om deze volgorde van beide kanten naar het midden te volgen en de extreme karakters te vergelijken. Als tot we het midden bereiken al onze karakters overeenkomen, dan hebben we een palindroom. Laten we een booleaanse methode validPalindrome(String s) maken om te controleren of String een palindroom is. Java-code is hier:

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);


   }

}

In de hoofdmethode controleren we op palindroomreeksen "niveau", "cool", "mevrouw" en "Nu, meneer, een oorlog is gewonnen!". Zoals je kunt zien, zijn de eerste, derde en vierde palindromen, maar de tweede niet. Wat gaat het programma opleveren? Dus de eerste is een palindroom, de tweede niet. Wat is er echter mis met de derde en vierde? Waarom is het resultaat onwaar ? U raadt waarschijnlijk al dat het punt is dat sommige tekens in deze tekenreeks hoofdletters zijn en sommige kleine letters, en voor Java zijn M en m twee verschillende tekens. Laten we het programma verbeteren om rekening te houden met dit verschil. Hier is een programma om te controleren of een string een palindroom is dat problemen met hoofdletters en kleine letters oplost.

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);


   }

}

Deze keer is het resultaat voor ons voorspelbaarder: Nou... niet bepaald voorspelbaar. De situatie met "Madam" wordt steeds beter, maar wat met ons lange en gelukkige palindroom "Nu, meneer, een oorlog is gewonnen!". Het is vrij eenvoudig, als u bedenkt dat alle spaties en leestekens hetzelfde zijn als letters voor Java. We moeten ons algoritme dus opnieuw verbeteren om dit overzicht te corrigeren. Laten we ons programma leren om spaties en interpunctie te negeren. Simpel gezegd negeren we alle niet-alfanumerieke tekens. Hier is het verbeterde palindroomprogramma in Java.

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);


   }

}

Het resultaat is in ieder geval wat we ervan verwachtten: Als u net begint met programmeren, is het misschien moeilijk voor u om te begrijpen hoe de stringtraversal- en vergelijkingsalgoritmen werken. Het is natuurlijk beter om hiermee om te gaan, maar je kunt een vereenvoudigde versie schrijven van de passage zelf door de reeks tekens, die in feite een string is. U kunt de methode StringBuffer.reverse gebruiken om te controleren of een string een palindroom is. Laten we de eenvoudigste versie doen zonder te controleren op niet-alfanumerieke symbolen en hoofdletters en kleine letters.

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);


   }
}

Het resultaat is hetzelfde als in het allereerste voorbeeld Als je wilt, kun je dit programma verbeteren zoals we deden met het eerste voorbeeld. Om te versterken wat je hebt geleerd, raden we je aan een videoles van onze Java-cursus te bekijken