[LeetCode] 5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

解法一：使用了在水中的鱼的博客看到的第一种思路（http://fisherlei.blogspot.com/2012/12/leetcode-longest-palindromic-substring.html），对于任意一个index，分别向前、向后查找可能的palindrome。因为palindrome有“aba”和“abba”两种形式，所以还需要照顾到当s[index]==s[index + 1]这种情况。时间复杂度 O(n^2)。代码如下：

	class Solution {
	public String longestPalindrome(String s) {
	if (s == null || s.length() == 0) {
	return "";
	}
	String longest = "";
	for (int i = 0; i < s.length(); i++) {
	if (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
	String temp1 = find(s, i, i + 1);
	if (temp1.length() > longest.length()) {
	longest = temp1;
	}
	}
	String temp2 = find(s, i, i);
	if (temp2.length() > longest.length()) {
	longest = temp2;
	}
	}
	return longest;
	}
	private String find(String s, int start, int end) {
	String longest = s.substring(start, end + 1);
	while (start - 1 >= 0 && end + 1 < s.length()
	&& s.charAt(start - 1) == s.charAt(end + 1)) {
	longest = s.substring(start - 1, end + 2);
	start = start - 1;
	end = end + 1;
	}
	return longest;
	}
	}

view raw longestPalindrome1.java hosted with ❤ by GitHub

明天再想想其他解法  \(▔▽▔)/