首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串

热度指数：250421 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

数据范围： $1 \le n \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n^2)$

进阶: 空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

"ababc"

输出

说明

最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入

"abbba"

输出

示例3

输入

"b"

输出

算法知识视频讲解

Javascript

王清江唷_全网同名

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string 字符串
 * @return int 整型
 */
function getLongestPalindrome(s) {
    //计算最长回文子串的长度，dp数组的含义   dp[i][j] 代表字符串 [i,j]的是不是回文字符串
    const dp = new Array(s.length).fill(0).map(_ => new Array(s.length).fill(false))
    let count = 0
    for (let i = s.length - 1; i >= 0; i--) {
        for (let j = i; j < s.length; j++) {
            if (s.charAt(i) === s.charAt(j)) {
                if (j - i <= 1) {
                    if (j - i + 1 > count) {
                        count = j - i + 1
                    }
                    dp[i][j] = true
                } else if (j - i > 1) {
                    if (dp[i + 1][j - 1]) {
                        if (j - i + 1 > count) {
                            count = j - i + 1
                        }
                    }
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }
        }
    }
    console.table(dp)
    return count
}

console.log(getLongestPalindrome("ccbcabaabba"));

发表于 2023-04-06 16:00:30 回复(0)

Javascript

Seauning

Javascript 中心扩散

function getLongestPalindrome( A ) {
    // write code here
    let max = 0;
    const palindrome = (l, r) =>{    // 中心扩散，找最长回文长度
        while(l >= 0 && r <= A.length) {
            if(A[l] !== A[r]) break;
            l--,r++;
        }
        return r - l - 1;    // 注意这个值的计算，因为最后一次扩散总是出界，或者不是回文，所以长度已经扩了需要减去
    }
    for(let i = 0; i < A.length; i++) {    // 简单遍历就好了
        max = Math.max(palindrome(i, i), max);            // 从一个点扩散
        max = Math.max(palindrome(i, i + 1), max);        // 从两个点扩散
    }
    return max;
}

发表于 2022-04-30 09:22:42 回复(0)

Javascript

messfairy

// 一、双中心检测法
function getLongestPalindrome0(A) {
	// write code here
	const n = A.length
	if (n === 1) {
		return A[0]
	}
	let maxLen = 0
	let subList = []
	for (let i = 0; i < n; i++) {
		let l, r
		for (l = i, r = i; A[l] === A[r] && l >= 0 && r < n; l--, r++) {}
		if (maxLen < r - l - 1) {
			maxLen = r - l - 1
			subList = [A.slice(l + 1, r)]
		} else if (maxLen === r - l - 1) {
			subList.push(A.slice(l + 1, r))
		}

		for (l = i, r = i + 1; A[l] === A[r] && l >= 0 && r < n; l--, r++) {}
		if (maxLen < r - l - 1) {
			maxLen = r - l - 1
			subList = [A.slice(l + 1, r)]
		} else if (maxLen === r - l - 1) {
			subList.push(A.slice(l + 1, r))
		}
	}

	return { maxLen, subList }
}

// 二、动态规划
function getLongestPalindrome(A) {
	const n = A.length
	const dp = []
	let maxLen = 0
	// let subList = []
	for (let i = 0; i < n; i++) {
		dp[i] = []
		dp[i][i] = 1
		// subList.push(A[i])
		maxLen = 1
	}
	for (let i = n - 1; i >= 0; i--) {
		for (let j = i + 1; j < n; j++) {
			if (A[i] === A[j]) {
				if (j - i <= 2) {
					dp[i][j] = j - i + 1
				} else {
					dp[i][j] = dp[i + 1][j - 1] + 2
				}
				if (maxLen < dp[i][j]) {
					maxLen = dp[i][j]
					// subList = [A.slice(i, j + 1)]
				}
				// else if (maxLen === dp[i][j]) {
				// 	subList.push(A.slice(i, j + 1))
				// }
			}
		}
	}

	return maxLen
	// return { maxLen, subList, dp: JSON.stringify(dp) }
}

发表于 2022-04-10 19:05:07 回复(0)

Javascript

牛客822067661号

function getLongestPalindrome(A) {
    let arr = A.split("")
    // 找出所有回文子串
    let resultArr = []
    while (arr.length > 0) {
        if (IsPalindrome([...arr])) {
            resultArr.push(arr.length)
            // Math.max()方法传入多个值
            return Math.max(...resultArr)
        } else {
            let len = MaxPalindrome([...arr])
            if (len > 1) {
                resultArr.push(len)
            }
            arr.shift()
        }
    }
}

// 判断已当前字母开头最大的回文长度
function MaxPalindrome(arr) {
    while (arr.length > 1) {
        arr.pop()
        if (IsPalindrome([...arr])) {
            return arr.length
        }
    }
}

// 判断当前数组是否为回文数组
function IsPalindrome(arr) {
    if (arr[0] === arr[arr.length - 1]) {
        let spliceArr = arr.splice(1, arr.length - 2)
        if (spliceArr.length >= 2) {
            return IsPalindrome(spliceArr)
        } else {
            return true
        }
    } else {
        return false
    }
}

找啊找，从头找到尾

发表于 2022-01-10 19:07:44 回复(0)

Javascript

要工作啊

哎呀，babcaaccabab, 这bcaaccab为什么不是8吗？揪心

发表于 2021-12-29 18:33:32 回复(0)

Javascript

牛客140967527号

function getLongestPalindrome( A ) {
    if (!A) { return 0; }
    
    const strLen = A.length;
    if (strLen < 2) { return 1; }
    if (strLen === 2) {
       return A.charAt(0) === A.charAt(1) ? 2 : 1;
    }
    
    const maxSize = A % 2 === 0 ? strLen - 1 : strLen;
    let maxSubLen = 1;
    
    const checkValid = (str) => {
       const len = str.length;
       const checkCount = len % 2 === 0 ? len / 2 : (len - 1) / 2;
       let result = true;
        
       for (let i = 0; i < checkCount; i++) {
          if (str.charAt(i) !== str.charAt(len - (i + 1))) {
              result = false;
              break;
          }
       }
        
       return result;
    }
    
    for (let j = 3; j <= maxSize; j += 1) {
        for (let i = 0; i + j <= strLen; i++) {
            const subStr = A.slice(i, i + j);
            const isValid = checkValid(subStr);
            if (isValid) {
                maxSubLen = Math.max(j, maxSubLen);
            }
        }
   }

   return maxSubLen;
}

发表于 2021-12-03 19:28:58 回复(0)

Javascript

美英

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A string字符串 
 * @return int整型
 */
function getLongestPalindrome( A ) {
    // write code here
    //需要改进成dp写法
    let max=1;
    for(let i=0;i<A.length;i++){
       for(let j = 1; j <=A.length; j++){
            let cur = A.substr(i,j)
            if(isP(cur)){
               max = Math.max(max,cur.length);
            }
       }
    }
    return max;
}
function isP(str){
    for(let i=0;i<str.length;i++){
        if(str[i]!=str[str.length-i-1]){
            return false
        }
    }
    return true
}
module.exports = {
    getLongestPalindrome : getLongestPalindrome
};

发表于 2021-12-02 22:00:07 回复(0)

Javascript

天网-__-

题目说有时间和空间都为O(n)的的解法。暂时没有找到。题解里面的都是n^2的复杂度。

第一种：动态规划。题解里面有不多说了

第二种：中心扩散。

可以优化的是，不需要分bab和baab两种情况。每次扩散的时候先向右推进到不等于中心元素的位置。然后在开始左右比较。复杂度：空间1 时间：n^2

function getLongestPalindrome( A ) {
    if (!A) {
        return ""
    };
    let res = 1;
    for (let i=0; i < A.length; ++i) {
        const r = symmetry(i, A);
        if (r > res) {
            res = r;
        }
    }
    return res;
}
function symmetry(pos, str) {
    let i = pos, j = pos - 1;
    while (i <= str.length && str[i] === str[pos]) {
        ++i;
    }
    while (i <= str.length && j >= 0 && str[i] === str[j]) {
        ++i;--j;
    }
    return i - j - 1;
}

发表于 2021-11-22 15:50:26 回复(0)

JavaScript

阿珊向前冲

export function getLongestPalindrome(A: string, n: number): number {
    // write code here
  let res = 1;
  for (let i = 0.5; i < A.length; i += 0.5) {
    let [left, right] = Number.isInteger(i) ? [i - 1, i + 1] : [i - 0.5, i + 0.5];
    for (; left >= 0 && right <= A.length - 1; left--, right++ ) {
      if (A.charAt(left) === A.charAt(right)) res = Math.max(right - left + 1, res);
      else break;
    }
  }
  return res;
}

发表于 2021-04-24 15:29:19 回复(0)

JavaScript

Newman1997

function getLongestPalindrome(A, n) {
    //中心扩散法
    function func(A,left,right){
        while(left>=0 && right<n && A[left]==A[right]){
            left--
            right++
        }
        return right-left+1-2
        //为什么还要减2  因为上面while循环终止了，此时A[left] != A[right]
        //所以此时的回文子串的左右边界其实是  l-1，  r+1
    } 
    
    let res=0
    for(let i=0;i<A.length;i++){
        // 区分奇偶字串
        res=Math.max(res,func(A,i,i),func(A,i,i+1))
    }
    return res
}

发表于 2021-03-31 17:40:44 回复(0)

JavaScript

别卷啦！

export function getLongestPalindrome(A: string, n: number): number {
    // write code here
   if(!n) return 0
    let res = 1
    const dp = []
    for(let i = n -1;i>=0;i--){
        dp[i] = []
        for(let j = i;j<n;j++){
            if(j - i == 0) dp[i][j] = true
            else if(A[i] == A[j]&&j-i == 1) dp[i][j] = true
            else if(A[i] == A[j] && dp[i+1][j-1]) dp[i][j] = true
            if( dp[i][j]&& j - i + 1 >res)  res = j - i + 1
        }
    }
        return res
}

发表于 2021-01-07 19:25:17 回复(0)

提交观点

问题信息

动态规划字符串

来自：经典算法题精讲（四）-...

上传者：牛客301499号

难度：

15条回答 2587收藏 68014浏览

通过挑战的用户

查看代码

牛客52206...

2023-03-12 11:49:39
牛客61316...

2023-03-11 21:34:19
小蛮妖

2023-03-09 16:16:00
牛客91815...

2023-03-08 15:23:26
牛客85121...

2023-03-08 15:07:36

最长回文子串

输入

输出

说明

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题