给你一个字符串s，找到s中最长的回文子串。

  1. 输入：s = "babad"
  2. 输出："bab"
  3. 解释："aba" 同样是符合题意的答案。

解题思路-暴力解法

通过两个for循环枚举所有的子串，一一进行回文串判断。因为切个字符串的开销比较大，所以我们选择记录起止位置，最后返回的时候才进行切割。这里我们使用go和rust来写，因为js通不过。
字符串分隔和切割操作 strings.Split 和使用[i:j]切片

import "strings"

func longestPalindrome(s string) string {
    length := len(s)
    if length < 2 {
        return s
    }
    maxLen,begin:=1,0
    sArray := strings.Split(s,"")
    for i:=0;i<length-1;i++{
        for j:=i+1;j<length;j++{
            if j-i+1 >maxLen && valid(sArray,i,j) { //这两个条件尽量把开销小的放在前面
                maxLen = j-i+1
                begin = i
            }
        }
    }
    return s[begin:begin+maxLen]
}
func valid(arr []string,i,j int) bool {
    for i<j {
        if arr[i]!=arr[j] {
            return false
        }
        i++
        j--
    }
    return true
}

for循环里面要传引用要不让所有权就被传走了；函数的参数不能直接改；字符串切片&s[i..j]切割字符串；

impl Solution {

pub fn longest_palindrome(s: String) -> String {
    let length = s.len();
    if length < 2 {
        return s;
    };
    let mut maxLen = 1;
    let mut begin = 0;
    let s_arr: Vec<char> = s.chars().collect();
    for i in 0..(length - 1) {
        for j in (i + 1)..length {
            if j - i + 1 > maxLen && Solution::valid(&s_arr, i, j) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    String::from(&s[begin..begin + maxLen])
}
    pub fn valid(arr: &Vec<char>, i: usize, j: usize) -> bool {
        let mut left = i;
        let mut right = j;
        while left < right {
            if arr[left] != arr[right] {
                return false;
            };
            left += 1;
            right -= 1;
        }
        true
    }
}

解题思路-中心扩散法

因为题目要找的是回文串，所以我们可以先枚举回文串的中心位置，再在中心位置去构建回文串，得到最长的那个回文串。
image.png

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = function(s) {
    let len = s.length
    if(len<2){
        return s
    }
      let begin = 0
    let maxLen = 1
      for(let i = 0;i<len;i++){
        let oddLen = valid(s,i,i)
      let evenLen = valid(s,i,i+1)
      let curLen = Math.max(oddLen,evenLen)
      if(curLen>maxLen){
          maxLen = curLen
        begin = i - parseInt((maxLen-1)/2) //为了兼容奇数长度和偶数情况 所以要减一再取int整数
      }
    }
      return s.substring(begin,begin+maxLen)
};
const valid = function(s,i,j){
    let len = s.length
    while(i>=0 && j<len){
        if(s[i]===s[j]){
          i--
        j++
      }else{
          break
      }
    }
      return j-i-1 //因为退出循环的时候i和j都不包括，所以长度要减一
}

import "strings"

func longestPalindrome(s string) string {
    lens := len(s)
    if lens<2{
        return s
    }
    begin,maxLen := 0,1
    s_arr := strings.Split(s,"")
    for i:=0;i<lens;i++ {
        oddLen := valid(s_arr,i,i)
        evenLen := valid(s_arr,i,i+1)
        curLen := max(oddLen,evenLen)
        if curLen > maxLen {
            maxLen = curLen
            begin = i - (maxLen-1)/2
        }
    }
    return s[begin:begin+maxLen]
}
func max(i,j int) int {
    if i>j {
        return i
    }
    return j
}
func valid(arr []string,i,j int){
    length := len(arr)
    for i>=0 && j<length {
        if arr[i] == arr[j] {
            i--
            j++
        }else{
            break
        }
    }
    return j-i-1
}

解题思路-动态规划

回文串具有天然的状态转移即一个回文串去掉两边的元素依然是回文，所以一个字符串是否是回文是有内部串和两边元素决定的。根据上述论据我们可以得到如下条件

  • 状态 我们dp[i][j] 表示s[i..j] 是否是回文
  • 状态转移方程 dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]
  • 边界条件 i+1和j-1这个区间严格小于2的时候没有意义即 j-1-(i+1)+1<2 => j - i < 3
  • 初始化dp[i][i] = trus
  • 填表方向，因为是参考左下方的值，所以可以先升序填列再升序填行 ```rust impl Solution { pub fn longest_palindrome(s: String) -> String {
      let (mut start, mut end) = (0, 0);
  let s = s.chars().collect::<Vec<_>>();
  let mut dp = vec![vec![false; s.len()]; s.len()];
  for i in (0..s.len()).rev() {
      for j in i..s.len() {
          if i == j || j - i == 1 && s[i] == s[j] {
              dp[i][j] = true;
          } else {
              dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
          }
          if dp[i][j] && j - i > end - start {
              start = i;
              end = j;
          }
      }
  }
  s[start..=end].iter().collect()
    } }

```