マージソートを使って文字列を辞書順を並べる

問題

B: さかさま辞書 - AtCoder Regular Contest 003 | AtCoder

解き方

この問題は以下のステップで解くことができる。

1. 全ての単語を前後反転させる
2. ソート
3. 更に前後反転し元に戻す

Javaの標準のソートメソッドを用いる

Javaには標準でArraysというクラスあり、ソートメソッドArrays.sort()が実装されている。このメソッドはジェネリックスを用いて実装されているので、数字以外でもソートが可能である。文字列をソートする場合は勝手に辞書順にソートしてくれる。

文字列を辞書順にソートするメソッドを実装する

Arrays.sort()の代わりにソートするメソッドを実装してみる。今回はマージソートを使用する。 文字列の辞書比較はStringクラスのcompareToメソッド用いる事で実装することができる。このメソッドの返り値が負の値であれば、レシーバに指定した文字列が辞書的に前にくる値となる。