5. 最长回文子串

class Solution {
public:
  string longestPalindrome(string s) {
    if (s.size() == 1)
      return s;

    int N = s.size();
    int Longest = 1;
    int Begin = 0;
    vector<vector<int>> DP(N, vector<int>(N));

    // Every single character is a palindrome.
    for (int i = 0; i < N; ++i)
      DP[i][i] = true;

    // Enumerate substrings [i..i + Len] from short to long.
    for (int Len = 2; Len <= N; ++Len) {
      for (int i = 0; i < N; ++i) {
        int j = Len + i - 1;
        if (j >= N)
          break;

        // Leftmost and rightmost character differs.
        if (s[i] != s[j]) {
          DP[i][j] = false;
        } else {
          // Special case for substrings with Len of 1 or 2.
          if (j - i <= 2)
            DP[i][j] = true;
          else
            DP[i][j] = DP[i + 1][j - 1];
        }

        // If substring [i..j] is already a palindrome.
        if (DP[i][j] && j - i + 1 > Longest) {
          Longest = j - i + 1;
          Begin = i;
        }
      }
    }

    return s.substr(Begin, Longest);
  }
};

class Solution {
public:
  string longestPalindrome(string s) {
    int N = s.size();
    int Longest = 1;
    int Begin = 0;
    // Enumerate the center of palindromes.
    for (int i = 0; i < N; ++i) {
      // Search for palindromes with odd length.
      int L = i;
      int R = i;
      while (L >= 0 && R < N) {
        if (s[L] != s[R])
          break;

        if (R - L + 1 > Longest) {
          Longest = R - L + 1;
          Begin = L;
        }
        --L;
        ++R;
      }
      // Search for palindromes with even length.
      L = i;
      R = i + 1;
      while (L >= 0 && R < N) {
        if (s[L] != s[R])
          break;

        if (R - L + 1 > Longest) {
          Longest = R - L + 1;
          Begin = L;
        }
        --L;
        ++R;
      }
    }
    return s.substr(Begin, Longest);
  }
};