英語の回文（palindrome）について調べてみた

みなさんご機嫌いかがでしょうか。今日は回文の話題です。回文(palindrome)とは何かご存知ない方も多いかとは思いますので、まずは簡単に回文についてご紹介します。

Contents

回文（palindrome）とは？

日本語の『たけやぶやけた』のように、上から読んでも下から読んでも同じ言葉になる語。英語では、例えばracecarやmadam等があり、palindrome及ばれている

１．Kayak　（カヤック）

２．Noon　（正午)

３．Stats　（統計）

４．Racecar (レースカー）

５．No Lemon, No Melon (レモンがなければメロンでない)

６．My gym (私のジム)

最も簡単な例ではありますが、回文かどうかを判定するアルゴリズムについて疑似コードを作ってみました。具体的なコードの実装に関しては、他サイトをご参照ください。総当たり法だとfor loop３回使って、O(n^3)かかりそうですが、動的計画法を使うと、O（n^2）で解けそうですね。

Step.1: String型でuserに好きな言葉をインプットしてもらう。

Step.2: 言葉をひっくり返す。

Step.3:ひっくり返した言葉と、もともとユーザーがインプットした言葉を比較

Step.4:もしひっくり返した言葉と、ユーザーがインプットした言葉が同じなら、”回文”とアウトプット

Step.5:そうでなければ、”回文ではない”とアウトプット

ということで今日はこんな感じです！