[leetcode]Longest Palindromic Substring

新博文地址：[leetcode]Longest Palindromic Substring

http://oj.leetcode.com/problems/longest-palindromic-substring/

 

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.

返回字符串中最长的回文子串。

本题略难啊.....

拿到本题的第一反应是：

* 1. find common subString of String s and its reverse s'
* 2. check if the common subString is palindromic ,if so , get the longest one

 即：首先把本题转换成比较熟悉的查找公共子串问题。

因为是回文串，其必要条件就是字符串s和它的逆序的公共子串。

再检查公共子串是不是回文串。比如abdeba，其逆序是abedba。公共子串是ab和ba，但是显然两个都不是回文子串。

好歹把代码写完了（很长，哎。。）写了几个测试实例也过了，但是提交时最长的case提示超时，囧。反正就是代码有问题啦。

拜读了一下leetcode中大神的代码，亮瞎狗眼啊.....<!--StartFragment-->

自己动手，老老实实将人家的代码码一遍吧╮(╯_╰)╭

 

 

	public String longestPalindromeDP(String s) {
		int length = s.length();
		if(length == 1){//长度为1时，直接返回
			return s;
		}
		int substringBeginIndex = 0;//记录最长回文子串的起始下标
		int maxLength = 0;//记录最长回文子串的长
		boolean[][] table = new boolean[length][length];//自己脑补一下这个table，功能一会儿就知道了
		for (int i = 0; i < length; i++) {
			table[i][i] = true;//单个字符肯定是回文的
			if (i < length - 1 && s.charAt(i) == s.charAt(i + 1)) {
				table[i][i + 1] = true;//2个相等字符也是回文的
				substringBeginIndex = i;
				maxLength = 2;
			}
		}
		//刚才已经讨论了最长子串为1 和 2 的情况，接下来讨论3 ~ length的情况
		for (int len = 3; len <= length; len++) {
			//对每一个可能的长度，从每一个字符开始讨论
			for (int i = 0; i < length - len + 1; i++) {
				int j = i + len - 1;//找到len子串end的下标
				if (s.charAt(i) == s.charAt(j) && table[i + 1][j - 1]) {
					//很明显，不啰嗦
					table[i][j] = true;
					substringBeginIndex = i;
					maxLength = len;
				}
			}
		}
		//完毕
		return s.substring(substringBeginIndex, maxLength + substringBeginIndex);
	}

上面大神的代码外层循环是从len开始loop，然后对每一个字符进行是否存在长度为len回文子串进行判断；

大家想一下，可不可以从每个字符进行loop，对每个len进行回文子串的判断。答案是不可行的。 

关于这道题目，还有更好的，空间复杂度为O(1)的算法，以及亮瞎狗眼的时间复杂度为O(1)的算法.....点这里