解答と解説: Reverse a String

「問題演習: Reverse a String」の解答編です。解答例を複数載せました。面接で思いついて欲しいのは解答例３ですが、解答例１から順に見ていきましょう。

解答例

Javaでの解答例です。

解答例１）

	public class Solution {
	public String reverseString(String s) {
	if (s == null) {
	return null;
	}
	int len = s.length();
	char[] cs = new char[len];
	for (int i = 0; i < len; i++) {
	cs[len - 1 - i] = s.charAt(i);
	}
	return new String(cs);
	}
	}

view raw reverse-a-string.java hosted with ❤ by GitHub

解答例２）

	public class Solution {
	public String reverseString(String s) {
	if (s == null) {
	return null;
	}
	int len = s.length();
	char[] cs = new char[len];
	for (int i = 0; i < len / 2; i++) {
	cs[i] = s.charAt(len - 1 - i);
	cs[len - 1 - i] = s.charAt(i);
	}
	if (len % 2 == 1) {
	cs[len / 2] = s.charAt(len / 2);
	}
	return new String(cs);
	}
	}

view raw reverse-a-string.java hosted with ❤ by GitHub

解答例３）

	public class Solution {
	public String reverseString(String s) {
	if (s == null) {
	return null;
	}
	char[] cs = new char[s.length()];
	int i = 0;
	int j = s.length() - 1;
	while (i <= j) {
	cs[i] = s.charAt(j);
	cs[j] = s.charAt(i);
	i++;
	j--;
	}
	return new String(cs);
	}
	}

view raw reverse-a-string.java hosted with ❤ by GitHub

解答例４）

	public class Solution {
	public String reverseString(String s) {
	if (s == null) {
	return null;
	}
	return new StringBuilder(s).reverse().toString();
	}
	}

view raw reverse-a-string.java hosted with ❤ by GitHub

解説

解答例１は、i 番目の文字を文字配列 cs の s.length() - 1 - i  番目に格納しています。この操作を 0 番目の文字列から s.length() - 1 番目まで繰り返すことで、文字配列 cs の中には逆順で文字を並べることができます。

基本的なアイデアは解答例１の方法で良いのですが、ここで気づいて欲しいのは i 番目の文字を文字配列 cs の s.length() - 1 - i  番目に格納ときに、同時に s.length() - 1 - i  番目の文字を cs の i 番目に格納しても良いということです。この操作によって for ループで操作する回数は半分に減らせます。これを実装したのが解答例２になります。

ただし、解答例２では文字列の長さが奇数のとき、真ん中の文字の処理を忘れないでください。解答例２の 12 ~ 14 行目に特殊な処理が入っているのはこのためです。このような特殊な処理は気付けない場合も多く、気付けたとしてもプログラムの記述でバグが入り込みやすいです。可能ならば特殊な処理が存在しないアルゴリズムを選びたいところです。

解答例３は特別な処理が存在せず、ループを回る回数も文字列の長さの半分に抑えることができています。この解法では、i と j の 2 つのインデックスを使って文字列を前後の両方から操作しています。

解答例４は、StringBuilder の reverse() メソッドを使っています。もし知っているならコードの記述量が短くミスが混入しにくいので使いたいところです。ただし、実際の面接でこの解法で解いたとしても、ループや再帰を使って効率良く解くアルゴリズムを求められるかもしれませんので、上記の他の解法も押さえておきましょう。

以上が今回の解説になります。

余談ですが、こちらの記事「JavaScriptの文字列を反転する１０の方法とそのパフォーマンス | 風と宇宙とプログラム」では他の解法と JavaScript でのパフォーマンスを示しています。面白い記事ですので紹介しておきます。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。