算法：LeetCode5. 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:

Input: "babad" Output: "bab"

Note: “aba” is also a valid answer.

Example:

Input: "cbbd" Output: "bb"

思路

這是個求最長回文子串的問題，回文就是正反字元串都一樣的字元串，比如aba,abba.首先想到将字元串反轉然後轉換成lcs（最長公共子串）的問題。然後發現是有問題的，S=“abacdfgdcaba”， 那麼S’ = “abacdgfdcaba”。 這樣S和S‘的最長公共子串是abacd。很明顯abacd并不是S的最長回文子串，它甚至連回文都不

是。

當原串S中含有一個非回文的串的反序串的時候，最長公共子串的解法就是不正确的。正如上一個例子中S既含有abacd，又含有abacd的反串cdaba，并且abacd又不是回文，是以轉化成為最長公共子串的方法不能成功

這個題目顯然使用dp來做的，這裡的dp主要用來判斷子串是不是回文，動态方程式：P（i，j）為1時代表字元串Si到Sj是一個回文，為0時代表字元串Si到Sj不是一個回文。初始化方程為：

P（i，i）= 1，P（i，i+1）=1 （S[i]= S[i+1]） 狀态轉移方程P（i，j）= P（i+1，j-1）（如果S[i] = S[j]）。

代碼

class Solution {
public:

    string longestPalindrome(string s) {
    int n = s.length();

  int longestBegin =;

  int maxLen =;

  bool table]] = {false};

  for (int i =; i < n; i++) {

    table[i][i] = true;   //前期的初始化

  }

  for (int i =; i < n; i++) {

    if (s[i] == s[i]) {

      table[i][i] = true; //前期的初始化

      longestBegin = i;

      maxLen =;

    }

  }
//周遊其他子串
  for (int len =; len <= n; len++) {

    for (int i =; i < n-len; i++) {

      int j = i+len;

      if (s[i] == s[j] && table[i][j]) {

        table[i][j] = true;

        longestBegin = i;

        maxLen = len;

      }

    }

  }

  return s.substr(longestBegin, maxLen);
    }
};