方法 Reverse 文字列 Java 再帰を使用する

このサンプル プログラムでは、ユーザーが入力した文字列を反転します。

文字列を反転する関数を作成します。 Later すべての文字が反転するまで、再帰的に呼び出します。この問題には再帰が適しています。なぜなら、反転した文字列は、元の文字列の末尾を反転させたもので、元の最初の文字が末尾に付いているだけであり、1文字少ないだけで同じ問題だからです。

書く Java プログラムする Reverse String

以下のクラスは、main() メソッドで入力値を宣言し、reverseString() メソッドに渡して、返された文字列を表示します。メソッド内の 2 つの println() 呼び出しにより、再帰処理の各ステップがコンソールに表示されます。

package com.guru99;
 
public class ReverseString {
 
	public static void main(String[] args) {
 
 
		String myStr = "Guru99";
 
 
		//create Method and pass and input parameter string 
		String reversed = reverseString(myStr);
		System.out.println("The reversed string is: " + reversed);
		
	}
 
 
	//Method take string parameter and check string is empty or not
	public static String reverseString(String myStr)
	{
		if (myStr.isEmpty()){
		 System.out.println("String in now Empty");	
		 return myStr;
		}
		//Calling Function Recursively
		System.out.println("String to be passed in Recursive Function: "+myStr.substring(1));
		return reverseString(myStr.substring(1)) + myStr.charAt(0);
	}
 
}

Code 出力：

出力の各行は、1つの再帰呼び出しを表しています。各行の末尾に表示される文字は、その上の行の文字より1文字短く、最後の行には逆の結果が表示されます。

String to be passed in Recursive Function: uru99
String to be passed in Recursive Function: ru99
String to be passed in Recursive Function: u99
String to be passed in Recursive Function: 99
String to be passed in Recursive Function: 9
String to be passed in Recursive Function: 
String in now Empty
The reversed string is: 99uruG

再帰的 Reversal Works ステップバイステップ

2行でメソッド全体が記述されています。基本ケースである if (myStr.isEmpty()) は、再帰を停止する場所を指定します。再帰行である return reverseString(myStr.substring(1)) + myStr.charAt(0) は、処理を 2 つに分割します。substring(1) は最初の文字以降のすべてであり、charAt(0) はその最初の文字に 1 を付加したものです。 After 逆順の剰余。

Trac入力 Guru99という数字が順序を明確に示している。 Java 連結処理が行われる前に、呼び出しごとに1つのフレームをプッシュします。

スタックは下から上に巻き戻され、各フレームが保存された文字を追加します。空の文字列は 9、次に 99、次に 99u、99ur、99uru、そして最後に 99uruG。 なぜなら Java 文字列は不変であり、これらの中間値はどれも前の値を上書きしません。連結するたびに新しいStringオブジェクトが割り当てられます。

コンソール出力には、注目すべき点が2つあります。6行目はコロンの後に何も表示されませんが、これは1文字の文字列に対してsubstring(1)を実行すると、nullではなく空文字列が返されるためです。それに続くメッセージは、元のプログラムでは「String in now Empty」となっています。これは「String is now empty」のスペルミスであり、コードと上記の出力が1行ずつ一致するようにそのまま残されています。

他の方法 Reverse 文字列 Java

再帰は最も明確な方法です 逆転現象は起こり得るが、実際の運用コードでそのような処理が行われることは稀である。3つの代替案でほぼすべての実際のケースを網羅できる。

1. StringBuilder.reverse() 最も短く、最も速い方法です。このクラスには組み込みの reverse() メソッドがあるため、処理全体を 1 行に収めることができます。

String reversed = new StringBuilder(myStr).reverse().toString();

2. charAt() を使用した for ループ 文字列を最後のインデックスから0まで逆方向にたどります。面接官は、ロジックを委譲するのではなく、そのロジックを示すために、このバージョンをしばしば要求します。

String reversed = "";
for (int i = myStr.length() - 1; i >= 0; i--) {
    reversed = reversed + myStr.charAt(i);
}

3. toCharArray() に対する 2 ポインタの交換 文字列を文字配列に変換し、ポインタが中央で一致するまで、最も外側の文字を内側に交換します。

char[] chars = myStr.toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
    char temp = chars[left];
    chars[left] = chars[right];
    chars[right] = temp;
    left++;
    right--;
}
String reversed = new String(chars);

同じ配列テクニックは数値シーケンスやその他の順序付きコレクションを反転させるため、 Java 配列 弦楽器の練習と同じくらい頻繁に練習を行う。

各手法の時間計算量と空間計算量

4つのバージョンはコストが同じではありません。以下の2つの2次式のエントリには共通する原因が1つあります。それは、ステップごとにまったく新しい文字列を作成し、n文字をn回コピーするとnの2乗の作業が必要になることです。

コールスタックの動作を学習または実証するには再帰バージョンを選択し、面接官がロジックを手作業で要求した場合は文字配列バージョンを選択し、出荷されるものにはStringBuilder.reverse()を選択します。教育用ソリューションと本番用ソリューションの間の同じトレードオフは、古典的な演習全体に現れます。 バブルソート フィボナッチ数列 〜へ 素数チェックそれぞれ練習する価値がある Java どちらの方法でも。

よくあるご質問