みなさんご機嫌いかがでしょうか。今日は回文の話題です。回文(palindrome)とは何かご存知ない方も多いかとは思いますので、まずは簡単に回文についてご紹介します。
Contents
回文（palindrome）とは？
日本語の『たけやぶやけた』のように、上から読んでも下から読んでも同じ言葉になる語。英語では、例えばracecarやmadam等があり、palindrome及ばれている
回文(palindrome)の例
１．Kayak （カヤック）
２．Noon （正午)
３．Stats （統計）
４．Racecar (レースカー）
５．No Lemon, No Melon (レモンがなければメロンでない)
６．My gym (私のジム)
回文(palindrome)のアルゴリズム
最も簡単な例ではありますが、回文かどうかを判定するアルゴリズムについて疑似コードを作ってみました。具体的なコードの実装に関しては、他サイトをご参照ください。総当たり法だとfor loop３回使って、O(n^3)かかりそうですが、動的計画法を使うと、O（n^2）で解けそうですね。
Step.1: String型でuserに好きな言葉をインプットしてもらう。
Step.2: 言葉をひっくり返す。
Step.3:ひっくり返した言葉と、もともとユーザーがインプットした言葉を比較
Step.4:もしひっくり返した言葉と、ユーザーがインプットした言葉が同じなら、”回文”とアウトプット
Step.5:そうでなければ、”回文ではない”とアウトプット
ということで今日はこんな感じです！