LeetCode5. Longest Palindromic Substring(动态规划)，

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”

---

二、动态规划算法DP

总体思想：要想知道长度为len的子串是否是回文，就要知道长度为len-2子串（len串的掐头去尾）是否为回文。而len-2子串可以通过前面计算保存判断结果查询即可（temp[i][j]）。

---

三、程序示例

C#版本

class Program
 {
      //动态规划算法，解决最长回文串问题
      public static string LongestPalindrome(string s)
      {
          if (s==null || s.Length==0)
          {
              return null;
          }
          bool[,] temp = new Boolean [s.Length, s.Length];

          //第一轮:[i,i]复制
          for (int i = 0; i < s.Length; i++)
          {
              temp[i, i] = true;
          }
          //第二轮:[i,i+1]
          int maxLen = 1;
          int begin = 0;
          int end = 0;

          for (int i = 0; i < s.Length-1; i++)
          {
              if (s[i] == s[i+1])
              {
                  temp[i, i + 1] = true;
                  maxLen = 2;
                  begin = i;
                  end = i + 1;
              }
          }

          //第三轮：三重循环
          for (int len = 2; len < s.Length; len++)
          {
              for (int i = 0; i + len < s.Length; i++)
              {
                  int j = i + len;
                  if (s[i] != s[j])
                  {
                      temp[i, j] = false;
                  }
                  else
                  {
                      if (temp[i+1,j-1])
                      {
                          temp[i, j] = true;
                          if (len + 1 > maxLen)
                          {
                              maxLen = len + 1;
                              begin = i;
                              end = j;
                          }
                      }
                      else
                      {
                          temp[i, j] = false;
                      }
                  }
              }
          }

          return s.Substring(begin, end-begin+1); 
      }

      static void Main(string[] args)
      {
          //string str = "abaaba";
          //string str = "eabcb";
          string str = "cbbd";
          string result = LongestPalindrome(str);
      }
  }