题目

给定一个字符串 s，返回它的最长回文子串。

image.png

解析

刚看到这个题目，还是慌了，完全不会。看答案。

对于一个字符串 s。假设有一个字串 s（i，j）(i<j)是回文串。我们记为 s[i][j] = true。
那么当 j-i >1 的时候， s[i-1][j-1]一定也是回文串。所以

(j-1 >1)   s[i][j] = s[i-1][j-1] & s[i] == s[j]
(j-1 <=1)  s[i][j] = s[i] == s[j]

s string
m := bool[][]

for (i=0;i<len-1;i++){
    m[i][i] = true
    if s[i] == s[i+1] {
      m[i][i+1] = true
      longest = 2
    }
}
s[len-1][len-1] = true

for (i = 0; i< len-1;i++) {
  for(j = i+2;j<len; j++){
         m[i][j] = m[i-1][j-1] && (s[i] == s[j])
         if m[i][j] && j-i >= longest {
          longest=j-i
        }
  }
}
return longest

上述代码的循环逻辑是错的，循环逻辑不应该是从头开始一直追溯到末尾。
首先知道 s[i][i]
然后知道 s[i][i+1]
然后知道 s[i][i+2]
...
最后 s[i][i+n]

所以最外层的循环是长度 length ，内层循环是从 0 到 len(s) - length。上界是 j 下界是 j+length

for (length = 3; i<= len;i++) {
  for (i=0;i<=len(s)-length;i++){
    m[i][i+length] = m[i+1][i-1+legnth] && s[i] == s[i+length]
    if m[i][i+length] && length > rst {
       rst = length
    }
  }
}

代码

func longestPalindrome(s string) string {
    
    if (len(s) <= 1) {
        return s
    }
    var il,ir int
    
    m:=make([][]bool, len(s))
    for i:=0; i< len(s)-1; i++ {
        m[i] = make([]bool, len(s))
        m[i][i] = true
        m[i][i+1] = s[i] == s[i+1]
        if m[i][i+1] {
            il = i
            ir = i+1
        }
    }
    m[len(s)-1] = make([]bool, len(s))
    m[len(s)-1][len(s)-1] = true
    
    for length:=3; length<=len(s); length++ {
        for left:=0; left <= len(s)-length; left++ {
            right := left+length-1
            m[left][right] = m[left+1][right-1] && s[left] == s[right]
            if m[left][right] {
                il = left
                ir = right
            }
        }
    }
    
    bts := []byte(s)
    rst := bts[il:ir+1]
    return string(rst)
}