LC5.最长回文字串

中心扩展法

主要思路是每次选一个中点，然后向两边扩展，找出以该中点对应的最长的回文串的长度，然后维护一个全局的最长回文串长度变量。

对于奇偶数长度的不同处理方式：

• expandAroundCenter方法中如果传入同一个点的索引，则表示以该点为中心，对应着探索字符串长度为奇数的情况
• 如果传入两个点的索引，则表示以这两个点之间为中心，对应着探索字符串长度为偶数的情况

/*** @Classname Solution5* @Description TODO* @Date 2019/12/9 9:45* @Created by Cheng*/
public class Solution5 {/*** 中心扩展法* @param s* @return*/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++) {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);}private int expandAroundCenter(String s, int left, int right) {int L = left, R = right;while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {L--;R++;}// 注意此时L和R都已经在有效范围外，所以长度是R-L-1return R - L - 1;}}

马拉车

具体思路有必要单独写一篇

/*** @Classname Solution5* @Description TODO* @Date 2019/12/9 9:45* @Created by Cheng*/
public class Solution5 {   /*** 马拉车* @param s* @return*/public static String longestPalindrome2(String s) {//处理字符串List<Character> list = new ArrayList<>();for (int i = 0; i < s.length(); i++) {list.add('#');list.add(s.charAt(i));}list.add('#');int[] dp = new int[list.size()];int resLen = 0;int resCenter = 0;int maxR = 0;int maxM = 0;for (int i = 1; i <list.size() ; i++) {dp[i] = maxR>i?Math.min(dp[maxM*2-i],maxR-i):1;while((i-dp[i])>=0 && (i+dp[i])<list.size() && list.get(i+dp[i]) == list.get(i-dp[i]))dp[i]++;if (i + dp[i] > maxR) {maxR = i+dp[i];maxM = i;}if (resLen < dp[i]) {resLen = dp[i];resCenter = i;}}StringBuilder ret = new StringBuilder();for (int i = resCenter-resLen+1; i <=resCenter+resLen-1 ; i++) {if(list.get(i)!='#')ret.append(list.get(i));}return ret.toString();}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！