647. 回文子串 dp+中心拓展法

647. 回文子串

難度：中等

2020/8/19每日一題打卡

題目描述

解題思路

1、動态規劃法

定義的狀态就是 dp[i][j]表示從i-j這個是不是回文

對于長度是一個字元的直接是回文，兩個字元的話就比較是不是相等

對于兩個以上，就看中間部分能不能組成回文串，然後比較兩邊是不是相等

dp[i][j] = dp[i+1][j-1] && dp[i] == dp[j]，要用到右邊的，是以第一層循環反着周遊

/*
			 * 647. 回文子串
			 * 2020/8/19
			 */
			 public int countSubstrings(String s) {
				 char[] str = s.toCharArray();
				 int n = s.length();
				 boolean[][] dp = new boolean[n][n]; //dp[i][j]表示從i-j這個是不是回文
				 int count = 0;
				 //dp[i][j] = dp[i+1][j-1] && dp[i] == dp[j]，要用到右邊的，是以第一層循環反着周遊
				 for (int i = n-1; i >= 0; i--) {
					for (int j = i; j < n; j++) {
						if(i == j) {
							dp[i][j] = true;
							count++;
						}else if(j - i == 1 && str[i] == str[j]){ //如果長度為2，比較字母是否相等
							dp[i][j] = true;
							count++;
						}else if(j - i > 1 && str[i] == str[j] && dp[i+1][j-1]){
							dp[i][j] = true;
							count++;
						}
						
					}
				}
				return count; 

			    }
           

2、中心拓展法

還有一種常見的判斷回文子串的方法，就是中心拓展法，以每一個位置為中心，想兩邊拓展，看能得到多少合法的回文子串

//中心拓展法
			 public int countSubstrings(String s) {
				 char[] str = s.toCharArray();
				 int count = 0;
				 for (int i = 0; i < str.length; i++) {
					count += isOk(str, i, i); //奇數
					count += isOk(str, i, i+1); //偶數
				}
				return count; 

			    }
			 
			 public int isOk(char[] str,int p,int q) {
				 int re = 0;
				while(p >= 0 && q < str.length) {
					if(str[p] == str[q]) {
						p--;q++;
						re++;
					}else {
						break;
					}
				}
				return re;
			 }