200 · Longest Palindromic Substring - LintCode

# Description

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.)

# Example

Example 1:

Input:"abcdzdcab"
Output:"cdzdc"

Example 2:

Input:"aba"
Output:"aba"

# Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

# Solution

# brute force solution

時間複雜度是 O (n^3) , n 為字符串長度
空間複雜度是 O (1), 只用到常數個臨時變量

	public class Solution {
	/**
	* @param s: input string
	* @return: a string as the longest palindromic substring
	*/
	public String longestPalindrome(String s) {
	// 暴力解

	int maxLen = 1;
	int start = 0;
	for (int i = 0; i < s.length() - 1; i++){
	for (int j = i + 1; j < s.length(); j++){
	if (j - i + 1 > maxLen && validPralindromic(s.toCharArray(), i, j)){
	maxLen = j - i + 1;
	start = i;
	}

	}
	}
	return s.substring(start, start + maxLen);

	}
	private boolean validPralindromic(char[] charArray, int left, int right){
	while (left < right){
	if (charArray[left] != charArray[right]){
	return false;
	}
	left++;
	right--;
	}
	return true;
	}
	}

# 中心擴散 enumeration

枚舉所有可能能回文子串的中心位置
要考慮回文子串的中心的奇偶性；中心可能是一個字符，或兩個相鄰的字符
記錄最長回文字串的相關變量

	public class Solution {
	/**
	* @param s: input string
	* @return: a string as the longest palindromic substring
	*/
	public String longestPalindrome(String s) {
	if (s.length() < 2){
	return s;
	}
	int maxlen = 1;
	int begin = 0;
	char[] charArray = s.toCharArray();


	for (int i = 0; i < s.length(); i++){
	int oddLen = expandCenter(charArray, i, i);
	int evenLen = expandCenter(charArray, i, i + 1);

	int charlen = Math.max(oddLen, evenLen);
	if (charlen > maxlen){
	maxlen = charlen;
	// 中心點，減去字符串長度 - 1 的一半，
	// ##@@center@@##
	// index: 0123 4 5678
	// 4 - (5 - 1) / 2 = 2 (第一個 @的位置)
	begin = i - (maxlen - 1) / 2;
	}
	}
	return s.substring(begin, begin + maxlen);

	}
	public int expandCenter(char[] charArray, int left, int right){
	while (left >= 0 && right < charArray.length){
	if (charArray[left] != charArray[right]){
	break;
	}
	left--;
	right++;
	}
	// 退出 while 時 #xxxxx#
	// left right 會在 #的位置
	return right - left - 1;
	}
	}

# 另一個寫法

	public class Solution {
	/**
	* @param s: input string
	* @return: a string as the longest palindromic substring
	*/
	public String longestPalindrome(String s) {
	if (s == null \|\| s.length() < 2) return s;
	int maxLen = 0;
	String result = null;
	for (int center = 0; center < s.length(); center++){
	int start = center, end = center;
	while (start >= 0 && end < s.length()){
	if (s.charAt(start) != s.charAt(end)){
	break;
	}
	int newLen = end - start + 1;
	if (newLen > maxLen){
	maxLen = newLen;
	result = s.substring(start, end + 1);
	}
	start--;
	end++;
	}

	int left = center, right = center + 1;
	while (left >= 0 && right < s.length())
	{
	if (s.charAt(left) != s.charAt(right)){
	break;
	}
	int newLen = right - left + 1;
	if (newLen > maxLen){
	maxLen = newLen;
	result = s.substring(left, right + 1);
	}
	left--;
	right++;
	}
	}
	return result;
	}

	}