5. Longest Palindromic Substring

• https://leetcode.com/problems/longest-palindromic-substring/solution/
• https://github.com/inohiro/LeetCode/tree/master/5_longest_palindromic_substring

与えられた文字列から最長の回文を見つけ出す。最長の部分文字列と同じやり方でいけるかなと思ってやったが、1000文字くらいの長い入力では TLE になってしまった。あと一歩という感じがしたが...

実装したアイデアは次のような感じ。回文だと最初の文字と最後の文字が等しい。そこで、2つの変数で文字の部分文字列の長さを伸ばしながら、同じ文字がきたらそれが回文なのか確認して候補とする。最初にこれを実装したあと、最長のものを求めるので、2つの変数は文字の配列の最初の要素と最後の要素から見ていけば良いことに気がついた。が、それでもダメ。最悪でも O(n²) な気がするが、うーん。

解説を読むと（やはり...）動的計画法でやるのがセオリーなようなので、明日実装してみる。悔しいなー、もう少しだったんだけど。これもよく出る問題な気がするから、マスターしたい。

---

追記（2017/11/08）

• https://github.com/inohiro/LeetCode/blob/master/5_longest_palindromic_substring/solution_1.rb

動的計画法ではない解法を実装してみたがいまいちよくわからない。絵を書きながら理解したい。動的計画法を用いた解法も実装する。