英語の回文(palindrome)について調べてみた

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

回文(palindrome)とは?

 

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

回文(palindrome)の例

 

1.Kayak (カヤック)

2.Noon (正午)

3.Stats (統計)

4.Racecar (レースカー)

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

6.My gym (私のジム)

 

回文(palindrome)のアルゴリズム

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

 

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

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

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

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

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

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