网站建设前期情况说明,公司建设网站有什么好处,做视频直播的网站,网站建设与规划案例想要精通算法和SQL的成长之路 - 最长回文子串 前言一. 最长回文子串1.1 中心扩散法的运用 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 最长回文子串
原题链接
1.1 中心扩散法的运用
这类具有回文性质的题目#xff0c;我们如果用常规的从左往右或者从右往左的遍历方… 想要精通算法和SQL的成长之路 - 最长回文子串 前言一. 最长回文子串1.1 中心扩散法的运用 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 最长回文子串
原题链接
1.1 中心扩散法的运用
这类具有回文性质的题目我们如果用常规的从左往右或者从右往左的遍历方式在编码上往往比较麻烦。那不妨我们以字符串中的每一个字符为起点同时向左右扩散判断左右的字符是否相等即中心扩散法往往这样更加通俗易懂。编码实现上也更为简单。
我们从左往右遍历字符串将每个字符串 s(i) 视为中心分别向左右扩散。先向左扩散排除掉和中心字符 s(i) 相同字符。判断条件s(left) s(i)。先向右扩散排除掉和中心字符 s(i) 相同字符。判断条件s(right) s(i)。再同时向左右扩散判断条件s(left) s(right)
public class Test5 {public String longestPalindrome(String s) {// 最长回文子串的起始位置int maxStart 0;// 左右指针以及数组长度。maxLen最长回文子串长度curLen当前的回文子串长度int left, right, len s.length(), maxLen 0, curLen 1;for (int i 0; i len; i) {left i - 1;right i 1;// 向左扩散去重while (left 0 s.charAt(left) s.charAt(i)) {left--;curLen;}// 向右扩散去重while (right len s.charAt(right) s.charAt(i)) {right;curLen;}// 同时向左右扩散while (left 0 right len s.charAt(left) s.charAt(right)) {left--;right;curLen 2;}// 更新最长回文子串长度和起始位置if (curLen maxLen) {maxLen curLen;maxStart left;}curLen 1;}// 截取字符串 最长回文子串起始位置 ~ 起始位置长度return s.substring(maxStart 1, maxStart maxLen 1);}
}
