每天一题LeetCode[第四天]

2019-11-11 02:18:58

字体：大中小

来源：转载

供稿：网友

每天一题LeetCode[第四天]

Longest Palindrome Substring

Description:

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"Subscribe to see which companies asked this question.

解题过程：

题意很简单，易于理解。关键是解题思路。一开始木有解题思路，只有一个穷举法，具体是，整体循环一次，然后每次判断当前i与剩下字符串是否有构成Palindrome的。问题，如何查找，就是findPalindrome(i,s.length()-1)反过来查找。但是效率真的不高。

看了TopSolution，才焕然大悟。。因为在相处第一个方法的时候，就一直走错方向。因为潜意识认为，提高效率的方向，很有可能是每一步的计算直接信息的利用，但是实在想不到，就去看TopSolution了。才发现原来，最开始的思路就错了，既然是Palindrome，那么有两种方式来判定一个字符串到底是不是Palindrome：

前后逼近判定法中间向两边的延伸的判定法(分奇数偶数两种)

而我却把全部思路都放到了第一种上，所以只能想到第一种解决方式。如果一开始换一个思路，说不定我能想出来。

java代码:

PRivate int firstIndex,maxLength=0; public String longestPalindrome(String s){ if(null==s || s.length()==0){ return ""; } if(s.length()==1){ return s; } // 一个一个尝试去查找 --从中间向两边查找 for(int i=0;i<s.length()-1;i++){ //奇数Palindrome查找 findPalindrome(s,i,i); //偶数Palindrome查找 findPalindrome(s,i,i+1); } return s.substring(firstIndex,firstIndex+maxLength); } private void findPalindrome(String s,int i,int j){ while (i>=0 && j<s.length()&& s.charAt(i)==s.charAt(j)){ i--; j++; } //这里注意，i,j出来都会多执行一次自减和自增 if(maxLength<j-i-1){ maxLength=j-i-1; firstIndex=i+1; } }

提高代码质量就是: 积累精美的思路，优质的细节的过程。

上一篇：Spring建立XML时候需要注意的问题

下一篇：Log4j2记录日志到数据库(MySQL&MongoDB)