回文字符串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
分析
本题最容易想到的一种方法应该就是中心扩散法。
中心扩散法怎么去找回文串?从每一个位置出发,向两边扩散即可。遇到不是回文的时候结束。
举个例子,str = "acdbbdaa"。我们需要寻找从第一个b(位置为3)出发最长回文串为多少。怎么寻找?
首先往左寻找与当期位置相同的字符,直到遇到不相等为止。
然后往右寻找与当期位置相同的字符,直到遇到不相等为止。
最后左右双向扩散,直到左和右不相等。如下图所示:
每个位置向两边扩散都会出现一个窗口大小(len)。如果len>maxLen(用来表示最长回文串的长度)。则更新maxLen的值。
因为我们最后要返回的是具体子串,而不是长度,因此,还需要记录一下maxLen时的起始位置(maxStart),即此时还要maxStart=len。
function longestPalindrome(str) { if (!str || str.length < 2) { return str; } const strLen = str.length; let maxStart = 0; let maxEnd = 0; let maxLen = 1; const cc = []; for (let r = 1; r < strLen; r++) { for (let l = 0; l < r; l++) { cc[l] = []; cc[l][r] = false; if (str.charAt(l) === str.charAt(r) && (r - l <= 2 || cc[l + 1][r - 1])) { cc[l][r] = true; if (r - l + 1 > maxLen) { maxLen = r - l + 1; maxStart = l; maxEnd = r; } } } } return str.substring(maxStart, maxEnd + 1); } var longestPalindrome = function (s) { if (!s || s.length < 2) { return s; } var s_f = s.split('').reverse().join(''); var resultStr = s[0]; var maxLen = 1; var tmpLen = 1; var maxStrIndex = 0; var len = s.length; //判断字符串是否回文 function ispalinerome(i, r) { if (len - i - 1 == r - tmpLen + 1) { return true } return false; } //初始化二维数组 var len = s.length; var arr = new Array(len); for (var i = 0; i < len; i++) { arr[i] = []; for (var r = 0; r < len; r++) { arr[i][r] = 0 } } for (var i = 0; i < len; i++) { for (var r = 0; r < len; r++) { if (s[i] == s_f[r]) { if (i == 0 || r == 0) { arr[i][r] = 1 } else { arr[i][r] = arr[i - 1][r - 1] + 1 tmpLen = arr[i][r] } if (tmpLen > maxLen && isPalinerome(i, r)) { maxStrIndex = r; maxLen = tmpLen; resultStr = s.substring(i - tmpLen + 1, i + 1); } } } } return resultStr; };
发表评论