FTPrep, 5 Longest Palindromic Substring

xiaoxiao2021-02-28  106

刚看到题,只有一个思路,以某个字母为中心向两边逐拓展的思路,然后这个中心从头到尾都过一遍,然后与之前的最优结果对比,进行更新。。参考了一下别人的代码结构,通过一个helper 方法,代码简单了不少,其实思路也应该是在不 中心不断移动的时候,都会去通过 helper函数找到该中心的最大自串。

要注意的点:

1,中心可以是单个字母,也可以是相邻的2个字母,这都符合palindromic,所以在i的取值范围上要主要,我没有取i=0,而i=0时,又只有一种情况,就是本身,在一开始就把这个特殊情况处理了。

2,helper 方法中,有个bug: return s.substring(left++, right); 这里大意了,left++ 和 left+1 在没有被其他函数方法调用时,都加1,效果是一样的,但是在被其他函数调用时,就不一样了,left++被调用时是调用了left,这个简单的道理就无需多言了,但还是习惯性的这么一写,bug,长经验了

3,  s.substring(left_index, right_index) ,这个用法很好,包括了left_index位置的字母,但是不包括 right_index的字母。

public class Solution { public String longestPalindrome(String s) { int len=s.length(); if(len==1||len==0) return s; int maxLen=0; String result=""; for(int i=1; i<len; i++){ String str1= Helper(s, i-1, i); String str2= Helper(s, i, i); String candidate=(str1.length()>str2.length())?str1:str2; result=(candidate.length()>result.length())?candidate:result; } return result; } public String Helper(String s, int left, int right){ while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){ left--; right++; } return s.substring(left+1, right); } }

转载请注明原文地址: https://www.6miu.com/read-28199.html

最新回复(0)