题目描述

原题链接

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

示例 1：

输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd” 输出：”bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

个人解法

JavaScript

function fun(s) {
    let i = 0;
    let j = s.length - 1;
    while(i < j){
        if(s[i] === s[j]){
            i ++;
            j --;
        }
        else {
            return false;
        }
    }
  return true;
}
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let str = '';
  let subStr = '';
  const length = s.length;
  if (length <= 0) {
    return "";
  }
  for (let i = 0; i < length; i++) {
    if (length - i < str.length) {
      break;
    }
    for (let j = i + 1; j <= length; j++) {
      if (j - i < str.length) {
        continue;
      }
      subStr = s.substring(i, j);
      if (fun(subStr)) {
        if (subStr.length > str.length) {
          str = subStr;
        }
      }
    }
  }
  return str;
};

Java（暴力解法）

大致思路就是从字串长度最大（字符串原始长度）开始找，每次减1，找到的第一个回文子串便是我们要的答案。
值得注意的是，我们在进行回文数判断的时候，拿事先取出的数组进行判断（将字符串转化为一个char数组）

class Solution {
    public String longestPalindrome(String s) {
        String longS = s.substring(0,1);
        char[] cs = s.toCharArray();
        int max = 1, j = 0,len=s.length();
        for(max=len;max>=1;max--){
            for(j=0;j<=len-max;j++){
                if (judge(cs,j, j + max-1)) {
                    longS=s.substring(j, j + max);
                    max=0;
                    break;
                }
            }
        }
            return longS;
        }
 private boolean judge(char[] cs, int i, int j) {
        while (i < j) {
            if (cs[i] != cs[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

更优解法

JavaScript

动态规划

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let str = '';
  const length = s.length;
  let arr = new Array(length);
  if (length <= 0) {
    return "";
  }
  if(length === 1){
      return s;
  }
  for (let i = 0; i < length; i++) {
    arr[i] = new Array(length);
  }
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      if (i === j) {
        arr[i][j] = true;
      }
      arr[i][j] = null;
    }
  }
  for (let L = 1; L <= length; L++) {
    for (let i = 0; i < length; i++) {
      let j = L + i - 1;
      if (j >= length) {
        break;
      }
      if (s[i] !== s[j]) {
        arr[i][j] = false;
      } else {
        if (j - i < 3) {
          arr[i][j] = true;
        } else {
          arr[i][j] = arr[i + 1][j - 1];
        }
      }
      if (arr[i][j] && j - i + 1 > str.length) {
        str = s.substring(i, j + 1);
      }
    }
  }
  return str;
};

中心扩散法

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
  let Resleft = 0;
  let Resright = 0;
  let maxLen = 0;
  let i = 0; //设i为中心的索引
  while (i < s.length) {
    let left = i - 1;
    while (left >= 0 && s[i] === s[left]) {
      left--;
    }
    let right = i + 1;
    while (right < s.length && s[i] === s[right]) {
      right++;
    }
    const end = right; //这里的right是右边第一个跟中心s[i]不相等的字符索引，保存下来，等会i直接跳到end处，可减少重复中心的计算
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    if (maxLen < right - left - 1) {
      maxLen = right - left - 1;
      Resleft = left + 1;
      Resright = right - 1;
    }
    i = end;
  }
  return s.substring(Resleft, Resright + 1);
};

Java

动态规划

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        //当长度为1时，直接返回s
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        //将字符串转化为字符数组，便于后面进行s字符串第i位和第j位的字符是否相等的判断
        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }
                //charArray[i] != charArray[j]代表s[i...j]必定不是回文串
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    //bb,aba 存在两种初始情况
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        //i位j位相等，s[i...j]是否为回文串取决于s[i+1...j-1]
                        //a bcb a（是）a bcd a（不是）
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

中心扩散法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            //初始中心可能是a b a（b是中心）也可能是a bb a（bb是中心）
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    //从初始中心开始拓展，如果是回文数，每次继续判断边界两位置字符是否一样
    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}