Java-program för att kontrollera en sträng är en palindrom

Vissa problem i programmering har status som klassiska. Vanligtvis är sådana uppgifter relaterade till matematik och de är mycket förtjusta i att fråga studenter på datavetenskapsspecialiteter, såväl som arbetssökande vid intervjuer. De är bra eftersom de hjälper till att sätta upp ditt tänkande på ett programmerare sätt ganska bra, samt träna det. Ett av dessa problem är att kontrollera om en sträng är ett palindrom, och vi kommer att överväga det i den här artikeln.

Vad är ett palindrom och varför kunna leta efter dem

Ett palindrom är en siffra, bokstavskombination, ord eller text som läses likadant åt båda hållen. För att sammanfatta kan en palindrom kallas vilken uppsättning tecken som helst som är symmetrisk kring dess mitt. Ordet kommer från grekiska rötter som bokstavligen härstammar från "springa tillbaka" (palin är "igen, tillbaka" och dromos, "springa"). Palindrom i Java betyder detsamma som i allmän betydelse. Exempel på palindromer:

• 1881
• aaqquqqaa
• pop
• Middag
• nivå
• Rotator
• Mitt gym
• Fru jag är Adam
• Nu, sir, ett krig är vunnet!

1881 är ett palindromnummer och de andra är palindromsträngar. I den här artikeln kommer vi att titta på palindromer som representeras som strängar, men vissa algoritmer är ganska tillämpliga på andra typer av palindromer i Java. Varför kanske du vill leta efter palindromer? Faktum är att vi inte ofta behöver leta efter palindromer i vardagen. Det är en väldigt specifik uppgift. Om vi ​​minns strängalgoritmer, oftare i praktiken, kan programmerare hitta sökning efter en delsträng i en sträng, och inte söka efter palindromer eller deras nummer. Problem relaterade till palindromer har dock viktiga tillämpningar. Den första är olympiadprogrammering. Det kan finnas uppgifter för att identifiera palindromer. Den andra applikationen som är relevant för nybörjare programmerare är intervjuer. Vid en teknisk intervju, du kan mycket väl bli ombedd att snabbt skriva ett program för att kontrollera om en sträng är palindrom, kanske till och med på ett papper. Tja, inom vetenskapen är den mest praktiska tillämpningen av att hitta palindromer biologiska algoritmer. Enligt Wikipedia spelar biologiska föreningars palindromicitet en viktig roll för egenskaperna hos olika biologiska föreningar.

Exempel på palindromalgoritmkod

Låt oss tänka efter. En sträng är en sekvens av tecken, kan man säga, en array av char. Det skulle vara mest logiskt att följa denna sekvens från båda sidor till mitten och jämföra de extrema karaktärerna. Om tills vi når mitten kommer alla våra karaktärer att matcha, då har vi ett palindrom. Låt oss skapa en boolesk metod validPalindrome(String s) för att kontrollera om String är palindrom. Java-koden finns här:

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


   }

}

I huvudmetoden kontrollerar vi efter palindromiska strängar "nivå", "cool", "Madam" och "Nu, sir, ett krig är vunnet!". Som du kan se är den första, tredje och fjärde palindromer, men den andra är det inte. Vad kommer programmet att ge? Så det första är ett palindrom, det andra är det inte. Men vad är det för fel på trean och fyran? Varför är resultatet falskt ? Du har förmodligen redan gissat att poängen är att vissa tecken i den här strängen är versaler och vissa är gemener, och för Java är M och m två olika tecken. Låt oss förbättra programmet för att ta hänsyn till denna skillnad. Här är ett program för att kontrollera om en sträng är ett palindrom som löser problem med stora och små bokstäver.

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


   }

}

Den här gången är resultatet mer förutsägbart för oss: Tja...inte direkt förutsägbart. Situationen med "Madam" blir bättre, men vad med vår långa och glada palindrom "Nu, sir, ett krig är vunnet!". Det är ganska enkelt, om du kommer ihåg att alla mellanslag och skiljetecken är samma som bokstäver för Java. Så vi måste förbättra vår algoritm igen för att rätta till denna förbiseende. Låt oss lära vårt program att ignorera mellanslag och skiljetecken. Enkelt uttryckt ignorerar vi alla icke-alfanumeriska tecken. Här är det förbättrade palindromprogrammet i 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);


   }

}

Resultatet är åtminstone vad vi förväntade oss av det: Om du precis har börjat programmera är det kanske svårt för dig att förstå hur strängtraversal- och jämförelsealgoritmerna fungerar. Naturligtvis är det bättre att ta itu med detta, men du kan skriva en förenklad version av själva passagen genom raden av tecken, som i själva verket är en sträng. Du kan använda metoden StringBuffer.reverse för att kontrollera om en sträng är en palindrom. Låt oss göra den enklaste versionen utan att leta efter icke-alfanumeriska symboler och stora och små bokstäver.

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


   }
}

Resultatet är detsamma som i det allra första exemplet Om du vill kan du förbättra det här programmet som vi gjorde med det första exemplet. För att förstärka det du lärde dig föreslår vi att du tittar på en videolektion från vår Java-kurs