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

やりたいこと

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」などといれても東京がサジェストされるのですが、
いったい彼らはどうやって実装してるんですかね。。。