文字列を左から右または右から左に読み始めても同じである場合、その文字列は回文であると言われます。この記事では、Java で文字列が回文であるかどうかを確認する方法を学びます。
そこで文字列を考えてみましょう str 、今のタスクは、その逆の文字列がそのままであることを確認することだけです。
回文の例:
入力： str = アバ
出力： はい入力： str = オタク
出力： いいえ
Java の回文文字列のメソッド
Java で文字列回文をチェックするには、以下に示す 3 つの主な方法があります。
クラスタリングとは何ですか
- 素朴な方法
- ツーポインタ方式
- 再帰的方法
- StringBuilder の使用
1. Java で回文文字列をチェックするための単純なアプローチ
指定された文字列を反転して比較します。元の文字列とその反転バージョンを比較することで、指定された文字列が回文であるかどうかを確認できます。
上記のアプローチの実装を以下に示します。
ジャワ // Java Program to implement // Basic Approach to check if // string is a Palindrome import java.io.*; // Driver Class class GFG { // main function public static boolean isPalindrome(String str) { // Initializing an empty string to store the reverse // of the original str String rev = ''; // Initializing a new boolean variable for the // answer boolean ans = false; for (int i = str.length() - 1; i>= 0; i--) { rev = rev + str.charAt(i); } // 両方の文字列が等しいかどうかを確認します if (str.equals(rev)) { ans = true; ans を返します。 } public static void main(String[] args) { // 入力文字列 String str = 'geeks'; // 文字列を小文字に変換します str = str.toLowerCase();ブール値 A = isPalindrome(str); System.out.println(A); } }>> 出力
false>
上記の方法の複雑さ:
時間計算量: 指定されたコードの時間計算量は O(n) です。ここで、n は入力文字列の長さです。これは、for ループが文字列内の各文字を 1 回反復して逆文字列を作成するためです。
空間の複雑さ: コードの空間計算量は O(n) です。ここで、n は入力文字列の長さです。これは、逆文字列が作成されて別の文字列変数に格納され、入力文字列の長さに比例してメモリ内のスペースが占有されるためです。さらに、コードで使用される他の変数 (i、str、および ans) は、入力サイズに関係なく、一定量のスペースを占有します。
インターフェースとは何ですか
上の例で次のように書くと、 アバ 代わりに アバ 、その後、次のように出力も取得する必要があります はい 。したがって、回文かどうかをチェックする前に、文字列の大文字と小文字を小文字または大文字に変更する必要があります。これを行わないと、予期しない結果が生じます。これは、コンパイラが文字に基づいて文字をチェックするためです。 アスキー 値と アスキー の値 あ と同じではありません ある 。
2. P に対する 2 ポインタ アプローチ Java での alindrome プログラム
私たちのアプローチは、まず文字列を小文字に変換することです。次に、2 つのポインタを取り上げます 私 文字列の先頭を指し、 j 文字列の終わりを指します。増加を続ける 私 そして減少します j その間 私
gimpの色変更
例 1:
ジャワ // Java program to check whether a // string is a Palindrome // Using two pointing variables // Main class public class GFG { // Method // Returning true if string is palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Method 2 // main driver method public static void main(String[] args) { // Input string String str = 'geeks'; // Convert the string to lowercase str = str.toLowerCase(); // passing bool function till holding true if (isPalindrome(str)) // It is a palindrome System.out.print('Yes'); else // Not a palindrome System.out.print('No'); } }> 出力
No>
上記の方法の複雑さ:
時間計算量: 指定されたコードの時間計算量は O(n) です。ここで、n は入力文字列の長さです。これは、while ループが文字列の半分を反復処理して回文かどうかを確認するためです。文字列の半分だけをチェックするため、反復回数は n/2、つまり O(n) に比例します。
空間の複雑さ: コードは入力サイズに関係なく一定量の追加スペースのみを使用するため、コードのスペース複雑度は O(1) です。コードで使用される変数は i、j、および str のみであり、それぞれ一定量のスペースを占有します。コード内に追加のスペースは作成されません。
例 2:
ジャワ // Java Program to check Whether // the String is Palindrome // or Not // Main class class GFG { // Method 1 // Returns true if string is a palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Main driver method public static void main(String[] args) { String str = 'geeks'; String str2 = 'RACEcar'; // Change strings to lowercase str = str.toLowerCase(); str2 = str2.toLowerCase(); // For string 1 System.out.print('String 1 :'); if (isPalindrome(str)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); // new line for better readability System.out.println(); // For string 2 System.out.print('String 2 :'); if (isPalindrome(str2)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); } }> 出力
String 1 :It is not a palindrome String 2 :It is a palindrome>
上記の方法の複雑さ:
時間計算量: 指定されたコードの時間計算量は O(n) です。ここで、n は入力文字列の長さです。これは、「isPalindrome」メソッドの while ループが文字列の半分を反復処理して、それが回文であるかどうかをチェックするためです。文字列の半分だけをチェックするため、反復回数は n/2、つまり O(n) に比例します。
空間の複雑さ: コードは入力サイズに関係なく一定量の追加スペースのみを使用するため、コードのスペース複雑度は O(1) です。コードで使用される変数は i、j、str、および str2 だけであり、それぞれ一定量のスペースを占有します。コード内に追加のスペースは作成されません。
3. P に対する再帰的アプローチ Java での alindrome プログラム
アプローチは非常にシンプルです。 2 ポインターのアプローチと同様に、文字列の最初と最後の値をチェックしますが、今回は再帰によって行われます。
ラテックスリスト
- 文字列の先頭を指す i と文字列の末尾を指す j の 2 つのポインターを取得します。
- i の間、i をインクリメントし、j をデクリメントし続けます。
- これらのポインタの文字が同じかどうかを確認してください。これを再帰を通じて行っています – (i+1, j-1
- i>=j 条件が満たされるまで、i 番目と j 番目のインデックス上のすべての文字が同じである場合は、true を出力し、それ以外の場合は false を出力します。
上記のアプローチの実装を以下に示します。
ジャワ // Java program to check whether a // string is a Palindrome using recursion import java.io.*; // Driver Class class GFG { public static boolean isPalindrome(int i, int j, String A) { // comparing the two pointers if (i>= j) { true を返します。 } // これらのポインター上の文字を比較します if (A.charAt(i) != A.charAt(j)) { return false; } // すべてを再帰的にチェックして return isPalindrome(i + 1, j - 1, A); public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // メイン関数 public static void main(String[] args) { // 入力文字列 String A = 'geeks'; // 文字列を小文字に変換します A = A.toLowerCase();ブール値 str = isPalindrome(A); System.out.println(str); } }>> 出力
false>
上記の方法の複雑さ:
時間計算量: 指定されたコードの時間計算量は O(n) です。ここで、n は入力文字列の長さです。これは、ポインタ i と j が交差するか、ポインタの文字が等しくなるまで、`isPalindrome` 関数が位置 (i+1, j-1) の文字に対してそれ自体を再帰的に呼び出すためです。文字列内の各文字を 1 回だけ比較するため、時間計算量は O(n) になります。
空間の複雑さ: コードの空間計算量は O(n) です。ここで、n は入力文字列の長さです。これは、再帰呼び出しごとに、関数パラメーターとローカル変数の現在の値を格納する新しいスタック フレームが作成されるためです。最悪の場合、関数呼び出しスタックは n/2 まで大きくなる可能性があるため (入力文字列が回文の場合)、空間計算量は O(n) になります。
4. Java での StringBuilder アプローチの使用
このアプローチでは、
ゲーム鳩アンドロイド
- まず、ユーザーから文字列入力を取得します。
- 次に、Stringbuilder オブジェクト str1 を作成し、そこに String の値を格納します。
- Stringbuider の reverse() メソッドは、逆の String を返します。ストリングを反転して str1 に格納します。
- equals() メソッドを使用して文字列の値を比較し、if 条件と else 条件を使用して文字列値が類似しているかどうかをチェックします。
上記のアプローチの実装を以下に示します。
ジャワ import java.util.Scanner; public class Main { public static void main(String[] args) { String str = 'GeeksForGeeks'; // String for testing StringBuilder str1 = new StringBuilder(str); str1.reverse(); if (str.equals(str1.toString())) { System.out.println('Palindrome String'); } else { System.out.println('Not a palindrome String'); } } }> 出力
Not a palindrome String>
上記のコードの複雑さ:
時間計算量: コードの時間計算量は O(n) です。ここでも、n は入力文字列 str の長さです。今回の複雑さに寄与する主な要因は、str1.reverse() を使用した文字列の反転です。この方法で文字列を反転すると、時間計算量は O(n) になります。ここで、n は文字列の長さです。入力の読み取りや文字列の比較など、コード内のその他の操作は定数時間の操作であり、全体の時間の複雑さには大きな影響を与えません。
空間の複雑さ: 指定された Java コードの空間計算量は O(n) です。ここで、n は入力文字列 str の長さです。これは、コードが StringBuilder を使用して入力文字列の反転コピーを保存し、StringBuilder に必要なスペースが入力文字列の長さに比例するためです。
参照
Palindrome の詳細については、を参照してください。 文字列回文のプログラム 。