Longest Palindromic Substring @LeetCode

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

	package leetcode.string;
	/**
	* Solution: 对每个string, 找中心(每个字符 和 每个空隙)，分别向两边扫描, 直到不是palindrome.
	* 这道题是比较常考的题目.基本思路是对于每个子串的中心
	*（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙）
	* 往两边同时进行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2*n-1(字符作为中心有n个，间隙有n-1个）。
	* 对于每个中心往两边扫描的复杂度为O(n),所以时间复杂度为O((2*n-1)*n)=O(n^2),空间复杂度为O(1)
	* i 对应 char 时候, left = right = 2 / i. 正好是从current char开始
	* i%2==1. a bc 正好是空隙，right = left + 1. 从a,b 开始。
	*
	* Solution2: DP.
	* 这个题目变形题很多，注意，好好看下Reference Huan Lin的原贴分析.
	*
	* Reference: http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html
	* @author jeffwan
	* @date Apr 15, 2014
	*/
	public class LongestPalindrome {
	public String longestPalindrome(String s) {
	if (s == null || s.length() == 0) {
	return "";
	}
	int length = s.length();
	int maxLength = 0;
	String result = "";
	for (int i = 0; i < 2 * length - 1; i++) {
	int left = i / 2;
	int right = i / 2;
	if (i % 2 == 1) {
	right = left + 1;
	}
	String str = findPalindrom(s, left, right);
	if (str.length() > maxLength) {
	maxLength = str.length();
	result = str;
	}
	}
	return result;
	}
	private String findPalindrom(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); // skip the non-equal char
	}
	}

view raw LongestPalindrome.java hosted with ❤ by GitHub