LeetCode #5. Longest Palindromic Substring プログラミング練習

問題：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

難易度:　medium
入力:　String
目的: 入力された文字列の中で一番長い回文を探せ
出力:　String
注意:　入力は最長で1000

palindromicは回文の意味です。
日本語で言うとトマトやしんぶんしなど、上から読んでも下から読んでも同じ文章を指します。

注意すべき事:　

• 文字数が奇数か偶数かで判断が違う（aba, abba）

• 入力が空文字列の場合があるので気を付けるように

• 入力が一文字の場合も回文なのでそのまま返す

• 全部違う文字が入力された時、最長の回文は任意の文字になるので頭文字を返しましょう

今回私が書いた方法は非常にストレートで、全体探索をしてしました。
以下回答です。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int right = 0;
        int left = 0;
        int maxlen = 0;
        if (len<2) return s;
        String result = s.substring(0,1);
        for (int i = 1; i<len; i++) {
            left = 1;
            right = 1;
            while (i-left >=0 && i+right < len && s.charAt(i-left) == s.charAt(i+right)) {
                if (maxlen < right+left+1) {
                        result = s.substring(i-left, i+right+1);
                        maxlen = right+left+1;
                }
                right++;
                left++;
            }
            left = 1;
            right = 0;
            while (i-left >=0 && i+right < len && s.charAt(i-left) == s.charAt(i+right)) {
                if (maxlen < right+left+1) {
                        result = s.substring(i-left, i+right+1);
                        maxlen = right+left;
                }
                right++;
                left++;
            }
        }
        return result;
    }
}

文字列をforで回し、i番目を中心に回文になっているかどうかを判断する方法です。
whileが二つあるのは奇数か偶数かで分けているからです。
Time complexityはO(n^2)
あまり賢いやり方ではないですね
Dynamic Programming でも行ける！っという声もあるのですが結局はO(n^2)なのでここでは紹介しません。
時間があったらO(n)で行けるかもう一回考えよ

では