LeetCode 5:Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

 

Example:

Input: "cbbd"

Output: "bb"

这题目首先要看清题意,palindromic是个啥玩意,一开始就没仔细看,以为只要找到首尾一样的字符就满足要求,然后找寻最大子串即可,是不对的;这里需要输出的是回文子串,也就是轴对称的,如果字符串由单数个字符组成,那就以最中间一个字符为轴,如果是双数个字符,那就以最中间两个字符中间为轴,更通俗一点该子串从左往右和从右往左是一样的

由以上可以考虑先找到对称轴的位置,然后分别向两遍扩张,left- -,right++,直到arr[left] != arr[right],中间的子串就为该轮循环回文子串,但是单数和双数得分开进行计算,最终只需要通过比较每轮得到的子串长度,得到最长子串

Java源码如下

package com.maoxiaomeng;

/**
* @author lihui
* @date 2018/3/25 11:29
*/
public class Solution {

private int start;
private int maxLen;

public void getPosAndLength(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}

//h e a b c d c b a f a
// l l l l r r r r
//h e a b c d d c b a f a
// l l l l l r r r r r

int subLen = right - left - 1;
if (subLen > maxLen) {
maxLen = subLen;
start = left + 1;
}
}

public String longestPalindrome(String s) {
int len = s.length();
if (len <= 1) {
return s;
}

for (int i = 0; i < len - 1; i++) {
getPosAndLength(s, i, i);
getPosAndLength(s, i, i + 1);
}
return s.substring(start, start + maxLen);
}
}

getPosAndLength方法后面两个参数分两种情况,如果s是单数字符,那么两个指针初始都同一个位置;如果双数,就相邻两个两边扩张;while里的条件顺序不能颠倒了,如果先判断两个字符相等,就会index越界,因为存在相同字符才有left- -,那么如果到了边界,最终left=-1就越界了,所以得先判断left和right,最终比较maxLen即可获取最大长度,同时子串起始位置要+1,因为上面–了

发表回复