字符串最长子串

题述

求一个子串的最长回文子串是常见算法题，所谓的回文子串就是正着读和反着读是一样的，其leetcode地址如下：
https://leetcode.com/problems/longest-palindromic-substring/

思路一

根据题述，我首先想到了穷举法，即找出字符串的所有子串，并验证其是否是回文子串来找到最长回文子串:

public String longestPalindromeIII(String s){if (s.length() == 0 || s.length() == 1) {return s;}int longestStr = 0;int longStart = 0;for (int i = 0; i < s.length(); i++) {for (int j = 0; j <= i; j++) {int start = j;int end = i;while (start <= end){if (s.charAt(start) == s.charAt(end)) {start++;end--;}else {break;}}if (start > end) {if (i - j + 1 > longestStr) {longestStr = i - j + 1;longStart = j;}}}}return s.substring(longStart, longestStr +longStart);}

穷举法在思路上最好理解，实现起来很简单，但是其时间复杂度达到了n^3，其空间复杂度为o(1)

思路二

分析回文子串的性质发现，所有的回文子串都是中心对称的，也就是说我们可以移动对称中心来实现遍历和检验，每一次移动中心后都从中心处开始向两边检验对称性，考虑到如果回文子串长度为偶数，则实际的对称中心是不存在子串中的，所以需要构造一个奇数的回文子串，这里采用了向每一个子串中间添加‘#’来处理

public String longestPalindrome(String s) {if (s.length() == 0) {return "";}int start = 0;//最大回文子串开始下标int end = 0;//最大回文子串结束下标int max = 0;//最大回文子串总长度//预处理子串，向其中添加‘#’String handleStr = preHandleStr(s);//i为回文中心点for (int i = 0; i < handleStr.length(); i++) {int step = 1;//step为回文中心单边长度while (i - step >= 0 && i + step < handleStr.length()){if (handleStr.charAt(i - step) == handleStr.charAt(i + step)) {if (step * 2 + 1 > max) {max = step * 2 + 1;start = i - step;end = i + step;}step++;}else {//这里主要是保证回文子串的最左和最右字符不能是我添加的‘#’，比如c#a#a，当回文中心为2或者3时其step都为2if (handleStr.charAt(start) == '#') {start++;end--;max-=2;}break;}}}return handleStr.substring(start, end + 1).replaceAll("#","");}private String preHandleStr(String s){if (s == null || s.length() == 0) {return "";}StringBuilder handleStr = new StringBuilder();handleStr.append(s.charAt(0));for (int i = 1; i < s.length(); i++) {handleStr.append("#").append(s.charAt(i));}return handleStr.toString();}

思路三

该思路主要是优化思路二，在思路二中，会存在这样一种情况，比如：
cabadabae以第四位的d为中心位置时，发现其最长回文的右边界为第7位，此时以第2位为中心的回文子串长度和以第6位为中心的回文子串长度都是3，以第3位为中心的回文子串长度和以第5位为中心的回文子串长度都是1，但是以第7位为中心的回文子串长度并不一定和以第1位为中心的回文子串长度相等，因为第8为数据是未知的。也就是说，只要当前回文中心坐标与当前对称可参照的回文长度和小于已知的最右边界，则可以不用计算本次回文中心对应的回文长度

代码实现

private String preHandleStr(String s){if (s == null || s.length() == 0) {return "";}StringBuilder handleStr = new StringBuilder();handleStr.append('#');for (int i = 0; i < s.length(); i++) {handleStr.append(s.charAt(i)).append("#");}return handleStr.toString();}/****/public String longestPalindromeII(String s){// 先预处理字符串String str = preHandleStr(s);// 处理后的字串长度int len = str.length();// 右边界int rightSide = 0;// 右边界对应的回文串中心int rightSideCenter = 0;// 保存以每个字符为中心的回文长度一半（向下取整）int[] halfLenArr = new int[len];// 记录回文中心int center = 0;// 记录最长回文长度int longestHalf = 0;for(int i = 0; i < len; i++) {// 是否需要中心扩展boolean needCalc = true;// 如果在右边界的覆盖之内if(rightSide > i) {// 计算相对rightSideCenter的对称位置int leftCenter = 2 * rightSideCenter - i;// 根据回文性质得到的结论halfLenArr[i] = halfLenArr[leftCenter];// 如果超过了右边界，进行调整if(i + halfLenArr[i] > rightSide) {halfLenArr[i] = rightSide - i;}// 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了if(i + halfLenArr[leftCenter] < rightSide) {// 直接推出结论needCalc = false;}}// 中心扩展if(needCalc) {while(i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {halfLenArr[i]++;} else {break;}}// 更新右边界及中心rightSide = i + halfLenArr[i];rightSideCenter = i;// 记录最长回文串if(halfLenArr[i] > longestHalf) {center = i;longestHalf = halfLenArr[i];}}}// 去掉之前添加的#StringBuffer sb = new StringBuffer();for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {sb.append(str.charAt(i));}return sb.toString();}

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