文字列が回文であることを確認する Java プログラム

プログラミングの問題の中には、古典的な問題として扱われているものもあります。通常、そのようなタスクは数学に関連しており、コンピュータ サイエンスを専門とする学生や求職者に面接で質問することを非常に好みます。これらは、プログラマの考え方を非常にうまく設定し、訓練するのに役立つため、優れています。このような問題の 1 つは、文字列が回文であるかどうかを確認する問題であり、この記事ではそれについて検討します。

回文とは何か、なぜ回文を探せるのか

回文とは、双方向で同じように読める数字、文字の組み合わせ、単語、またはテキストです。要約すると、回文は、その中央に対して対称な文字のセットと呼ぶことができます。この言葉はギリシャ語の語源で、文字通り「逃げる」に由来します（ペイリンは「再び、戻る」、ドロモスは「走る」）。Java での回文は、一般的な意味と同じ意味です。回文の例:

• 1881年
• ああああああ
• ポップ
• 昼
• レベル
• ローテータ
• 私のジム
• マダム、私はアダムです
• さあ、先生、戦争は勝ちました！

1881 は回文数字で、その他は回文文字列です。この記事では、文字列として表現される回文について説明しますが、一部のアルゴリズムは Java の他の種類の回文にも適用できます。なぜ回文を探す必要があるのでしょうか? 実際、日常生活の中で回文を探す必要はあまりありません。それは非常に具体的なタスクです。文字列アルゴリズムを思い出してみると、実際には、プログラマーは回文やその番号を検索するのではなく、文字列内の部分文字列を検索することがよくあります。ただし、回文に関連する問題には重要な用途があります。1つ目はオリンピックのプログラムです。回文を識別するタスクがある可能性があります。初心者プログラマーに関連する 2 番目のアプリケーションは面接です。技術面接では、文字列が回文かどうかをチェックするプログラムを、場合によっては紙にでも簡単に書くよう求められるかもしれません。科学において、回文を見つけるための最も実際的な応用は生物学的アルゴリズムです。Wikipedia によると、生物学的化合物の回文性は、さまざまな生物学的化合物の特性において重要な役割を果たしています。

回文アルゴリズムのコード例

考えましょう。文字列は文字のシーケンスであり、char の配列とも言えます。この順序を両側から中央までたどって、極端なキャラクターを比較するのが最も合理的です。中央に到達するまでにすべての文字が一致する場合、回文が完成します。String が回文かどうかを確認するためのブール値メソッド validPalindrome(String s) を作成しましょう。Java コードは次のとおりです。

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


   }

}

main メソッドでは、回文文字列「level」、「cool」、「Madam」、および「Now, sir, a war is win!」をチェックします。ご覧のとおり、1 番目、3 番目、4 番目は回文ですが、2 番目は回文ではありません。プログラムは何を与えるのでしょうか？ つまり、最初のものは回文ですが、2 番目のものは回文ではありません。しかし、3番目と4番目の何が問題なのでしょうか？結果がfalseになるのはなぜですか? おそらくすでにお気づきかと思いますが、要点は、この文字列の一部の文字は大文字で、一部の文字は小文字であり、Java の場合、M と m は 2 つの異なる文字であるということです。この違いを考慮してプログラムを改良してみましょう。これは、文字列が大文字と小文字の問題を解決する回文であるかどうかをチェックするプログラムです。

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


   }

}

今回の結果は、私たちにとってより予測可能です。 うーん…正確には予測できません。「マダム」の状況は改善しつつありますが、「さあ、先生、戦争は勝ちました！」という長くて幸せな回文はどうでしょうか。すべてのスペースと句読点記号は Java の文字と同じであることを覚えていれば、これは非常に簡単です。したがって、この見落としを修正するためにアルゴリズムを再度改善する必要があります。スペースと句読点を無視するようにプログラムに教えてみましょう。簡単に言えば、英数字以外の文字はすべて無視されます。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);


   }

}

少なくとも、結果は私たちが期待したとおりです。 おそらく、プログラミングを始めたばかりの場合、文字列の走査と比較のアルゴリズムがどのように機能するかを理解するのは難しいでしょう。もちろん、これに対処する方が良いですが、実際には文字列である文字の配列を通過する部分の簡略化したバージョンを作成することもできます。StringBuffer.reverse メソッドを使用して、文字列が回文であるかどうかを確認できます。英数字以外の記号や大文字と小文字をチェックしない最も単純なバージョンを実行してみましょう。

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


   }
}

結果は最初の例と同じです 必要に応じて、最初の例で行ったようにこのプログラムを改良することもできます。 学んだことをさらに強化するには、Java コースのビデオ レッスンを視聴することをお勧めします。