検索エンジンを実装するにあたり、「とう」や「tok」、「東」というインプットから「東京」という結果をサジェストして欲しい

下記を実現するにはどうやるのがよいでしょうか？
自分なりに考えた実現方法案も後述しましたので、それらも参考にしていただけると幸いです。
よろしくお願いします。

やりたいこと

APIのパラメーターで文字列を渡す。それをキーにテキストリストから検索をしたい。
具体的には、「とう」や「tok」、「東」というインプットにたいして、
後述の都道府県リストから「東京」という結果を取得したい。
「とう」のときに「糖分」がひっかかるのはOK

単語リスト

東京
京都
大阪
北海道
福岡
糖分

※ 文章ではなくて、すでに単語レベルにパースされてるという前提で大丈夫です
※ レコード数は多くても数百(パフォーマンスは問題にならないかと）

環境

Rails 4.2.6
AWS EC2 + RDS for MYSQL 5.7

実現方法案

1. 普通にMySQLでlike検索
   「東」と入力しないとひっかからない
   平仮名、アルファベットのカラムを用意してそこからもlike検索をすれば、
   平仮名でもアルファベットでもOK?
   ※ レコード数は多くないので、速度は気にしません。
   ※ kakasiが使えそう

2. MySQL5.7でのfull-text index
   1と同様で、平仮名、アルファベット、漢字のそれぞれの転置インデックスを作らないとダメ。
   ※ 参考までに、RDSではNグラムパーサーしか使えません。

3. Elastic search
   いれるのが大変そう(試してない）。今回はそこまでコストかけずに実装したい
   Kuromojiをいれれば、漢字と読みの紐付けはできる

4. 他になにかあれば

その他

googleだと検索する時に「とうky」などといれても東京がサジェストされるのですが、
いったい彼らはどうやって実装してるんですかね。。。