[leetcode] 5. Longest Palindromic Substring (Medium)

原题链接

---

找到并返回最长回路子串

思路：
解法一：
最简单的双重遍历，判断s[i]到s[j]是不是回串。
Runtime: 610 ms, faster than 6.39% of Java 慢的不行

class Solution {public String longestPalindrome(String s) {int len=s.length();for (int i = 0; i < len; i++) {int subNum = i + 1;int subLen = len - i;for (int j = 0; j < subNum; j++) {String subStr = s.substring(j, j + subLen);if (isPalindrome(subStr))return subStr;}}return "";}public boolean isPalindrome(String s){int beg = 0, end = s.length() - 1;while(beg<end){if(s.charAt(beg)!=s.charAt(end))return false;beg++;end--;}return true;}}

解法二：
遍历一次，以每一个s[i]为中心，计算。
Runtime: 4 ms, faster than 100.00% of Java

class Solution {int len = 0, maxLength = 0, start = 0;public String longestPalindrome(String s) {char[] arr = s.toCharArray();len = s.length();if (len <= 1)return s;for (int i = 0; i < len; i++) {i = helper(arr, i);}return s.substring(start, start + maxLength);}public int helper(char[] arr, int k) {int i = k - 1, j = k;while (j < len - 1 && arr[j] == arr[j + 1])j++;int nextCenter = j++;while (i >= 0 && j < len && arr[i] == arr[j]) {i--;j++;}if (j - i - 1 > maxLength) {maxLength = j - i - 1;start = i + 1;}return nextCenter;}}