Longest Palindromic Substring 最長回文子串

之前不知道為什麼沒太想明白，想明白了之後覺得其實還是挺容易的。大概記錄一下思路。

其實就是簡單的從兩個相同的字元開始找起而已。

第一次找類似于"aa"，"bb"這樣的結構。這裡需要注意的就是當判斷‘aa’的時候，‘aa’結構對應的是table[i+1][j-1]

舉例來說，如果i為0，j為1，也就是table[1][0]，當你的原始字串是類似于’aba‘的結構的時候，是不會有這樣的問題的，aba的時候，判斷table的值得時候會落在b上。而b是自己的回文。是以要提前指派給table[i][i-1]。

然後接着判斷有沒有abba這樣的結構，然後是abbccbba....就這麼一個循環的過程。記錄最長就好了。

在網上浏覽的時候完全被大家畫的矩陣搞暈了。是個矩陣，當你想明白之後看矩陣也會覺得很清晰。但是，我覺得闡述思路是更重要的。

比如

a	a
a	1	1
a	1

 這裡就是要把最下面那個0變成1

a	b	c	e	c	a
a	1
b	1
c	1
e	1
c	1	1
a	1

很容易看出最長子串在哪裡了吧？（為了容易了解我沒有加上特殊條件table[i][i-1] = 1）

private static String findSub(String str) {
		// TODO Auto-generated method stub
		int length = str.length();
		boolean table[][] = new boolean[length][length];
		
		int start=0, end=0,longest = 0;
		
		table[0][0] = true;
		for(int i=1; i < length; i++)
		{
			table[i][i] = true;
			table[i][i-1] = true;//abba這樣的substring需要
		}
		
		for(int k = 2; k <= length; k++)//substring length
		{
			for(int i = 0; i <= length-k; i++)
			{
				int j = i+k-1;
				
				if(str.charAt(i)==str.charAt(j) && table[i+1][j-1] == true)
				{
					table[i][j]=true;
					if(longest < k)
					{
						longest = k;
						start = i;
						end = j+1;
					}
				}
			}
		}
		
		str = str.substring(start,end);
		return str;
	}