解答と解説: Reverse a String

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

解答例

Javaでの解答例です。

解答例1)

解答例2)

解答例3)

解答例4)

解説

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

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

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

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

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

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

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

このエントリーをはてなブックマークに追加

コメント

このブログの人気の投稿

問題演習: Hamming Weight

解答と解説: Max Depth of Binary Tree

問題演習: Find Max Element per Level in Binary Tree