LeetCode(6) 最长回文字符串

题目：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

思路：

看到这道题目，首先想到回文字符串，是一个沿正中字符串对称的字符串，一个字符串如果时回文字符串，去除两端的字符串也必为回文字符串，由此设中间的字符串为子状态，应该可以用动态规划的方式求解。这里设置储存状态的数组为dpi,为字符串（i~j）子串是否为回文字符串。编程思路如下：

具体代码如下所示：
定义了一个paliInfo结构体，用于储存最长子串的信息。相比起光放给出的算法删除了对于j>i部分的循环。实际的运行结果中，也体现出了这一点，比起官方的节省了差不多一半的时间，和空间。

官方动态规划运行结果

个人的动态规划结果

type paliInfo struct {
   size int
 start int
 end int
}
func longestPalindrome(s string) string{
   //1.设定数组保存回文字符串信息
 n := len(s)
   dp := make([][]bool,n)
   for k := 0;k<n;k++{
      dp[k] = make ([]bool,n)
   }
   var ans paliInfo
 //2.如果一个字符串中i~j为回文字符串，则（i+1）~（j-1）为回文字符串
 //3.第一个字符和第二个字符的回文字符串不可以用此判断,设置初始值
 for i:=0;i<n;i++{
      dp[i][i] = true
 }
   ans.size = 1
 ans.start = 0
 ans.end = 0
 for i := 0;i<n;i++{
      for j := i-1;j>=0;j--{
         if i-j == 1{
            if s[i] == s[j]{
               dp[j][i] = true
 if i-j+1>ans.size{
                  ans.start = j
                  ans.end = i
                  ans.size =i-j+1
 }
            } else {
               dp[j][i]=false
 }
         }
         if i-j >1{
            if dp[j+1][i-1]&&s[i]==s[j]{
               dp[j][i]=true
 if i-j+1>ans.size{
                  ans.start = j
                  ans.end = i
                  ans.size =i-j+1
 }
            }else {
               dp[j][i]=false
 }
         }
      }
   }
   return s[ans.start:ans.end+1]
}

有疑问加站长微信联系（非本文作者）