LeetCode(6) 最长回文字符串

LeetCode(6) 最长回文字符串

4 years ago

source link: https://studygolang.com/articles/31389
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目：

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

思路：

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

MZrqy2m.png!mobile

具体代码如下所示：

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

VNBJrir.png!mobile

官方动态规划运行结果

z2auI3Y.png!mobile

个人的动态规划结果

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]
}

有疑问加站长微信联系