【問題描述】[中等]

【解答思路】

1. 暴力

首先明確如何判斷一個字符串是否為回文字符串。第一個字符與最后一個字符相同，第二個字符與倒數第二個字符相同…關于中心位置軸對稱。
本題要求一共有多少個回文子串，那么就需要判斷，索引[i, j]的子串是不是回文子串，遍歷所有這樣[i, j]進行判斷就可以找到回文子串的總數。這是暴力的做法。
首先如何判斷[i, j]的子串是回文串，根據定義來判斷即可。
定義boolean isPalindrome(char[] chars, int start, int end)，第一個參數為原字符串的字符數組表示，第二第三個參數分別是字串的開始與結束索引。
在區間[start, end]上進行雙指針的掃描，將關于中心位置對應的字符進行比較，如果發現有不相等說明不是回文子串。
循環結束沒有發現對應位置不相等的字符，說明是回文串。
主函數中
外循環的i表示子串的長度，子串最長為s.length()，所以循環的條件為i <= s.length()。從長度2開始是因為，長度為1的子串都是回文子串，一共有s.length()個，最后加上即可。
內循環j表示子串的開始索引，那么其結束索引為j + i - 1。調用函數isPalindrome進行判斷。
最后返回result + s.length()，將長度為1的子串都是回文子串的計數也算進行。

時間復雜度：O(N³) 空間復雜度：O(1)

public int countSubstrings(String s) {char[] chars = s.toCharArray();int result = 0;for (int i = 2; i <= s.length(); i++) {for (int j = 0; j + i - 1 < s.length(); j++)if (isPalindrome(chars, j, j + i - 1))result++;}return result + s.length();}private boolean isPalindrome(char[] chars, int start, int end) {for (int i = start, j = end; j > i; i++, j--) {if (chars[i] != chars[j])return false;}return true;}

2. 中心擴展

回文字符串關于中心對稱，這個中心既可以是一個字符（比如子串的長度為奇數時），也可以是兩個字符的中間（比如子串的長度為偶數時）。那么對于長度為n的字符串，其子串的中心一共有**n+（n-1）**個，n個是字母，n-1個是兩個字母的間歇。
我們需要找到每一個可能的對稱中心有能向外擴展出多少個回文子串。要想辦法表示每一個回文中心，外擴的方式都一樣。
回文中心與子串的奇偶性有關，想必要分情況討論。
如果子串的長度為奇數，那么第一個子串只有一個字符，其左邊界left與右邊界right相等。
如果子串的長度為偶數，那么第一個子串有兩個字符，其左邊界left與右邊界right的關系為right = left + 1。
所以可以通過奇偶性來控制初始時left與right的關系。
循環 for (int i = 0; i < chars.length * 2 - 1; i++)，i表示每一個可能的回文中心，通過i的奇偶性來設置初始的left, right。內循環進行外擴，首先保證索引不超過數組邊界，其次當前判斷的兩個字符相等。否則，當前[left, right]不是回文子串，向外擴的也不可能是。外擴的方式就是使left–, right++。

時間復雜度：O(N²) 空間復雜度：O(1)

public int countSubstrings3(String s) {char[] chars = s.toCharArray();int result = 0;for (int i = 0; i < chars.length * 2 - 1; i++) { // 對每個可能的回文中心進行循環int left = i / 2; // 當中心是兩個字母的間歇時i%2 = 1；當中心是字母時 left==right都落在該字母的位置int right = left + i % 2;while(left >= 0 && right < chars.length && chars[left] == chars[right]){left--;right++;result++;}}return result;}

3. 動態規劃

動態規劃流程
第 1 步：設計狀態
dp[i][j] i開始j結尾的是否為回文字符串
第 2 步：狀態轉移方程

for(int i = s.length()-1; i>=0; i--){for(int j = i+1; j<s.length(); j++){if(s.charAt(i) == s.charAt(j)){//i和j相鄰的時候if(j - i == 1){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1]}}else{dp[i][j] = false;}} }

第 3 步：考慮初始化

第 4 步：考慮輸出
統計 dp[i][j] = T 的個數

時間復雜度：O(N) 空間復雜度：O(1)

class Solution {public int countSubstrings(String s) {if(s == null || s.equals("")){return 0;}int n = s.length();boolean[][] dp = new boolean[n][n];int result = s.length();for(int i = 0; i<n; i++) dp[i][i] = true;for(int i = n-1; i>=0; i--){for(int j = i+1; j<n; j++){if(s.charAt(i) == s.charAt(j)) {//i和j相鄰的時候if(j-i == 1){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1]; }}else{dp[i][j] = false;}if(dp[i][j]){result++;}}}return result;} }

2. Manacher 算法

時間復雜度：O(N) 空間復雜度：O(1)

class Solution {public int countSubstrings(String s) {int n = s.length();StringBuffer t = new StringBuffer("$#");for (int i = 0; i < n; ++i) {t.append(s.charAt(i));t.append('#');}n = t.length();t.append('!');int[] f = new int[n];int iMax = 0, rMax = 0, ans = 0;for (int i = 1; i < n; ++i) {// 初始化 f[i]f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;// 中心拓展while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {++f[i];}// 動態維護 iMax 和 rMaxif (i + f[i] - 1 > rMax) {iMax = i;rMax = i + f[i] - 1;}// 統計答案, 當前貢獻為 (f[i] - 1) / 2 上取整ans += f[i] / 2;}return ans;} }

【總結】

1. 動態規劃流程

第 1 步：設計狀態
第 2 步：狀態轉移方程
第 3 步：考慮初始化
第 4 步：考慮輸出
第 5 步：考慮是否可以狀態壓縮

2.暫時沒有掌握 Manacher 算法（馬拉車）

2.1 加# 變奇數長度 收尾加標識
2.2 初始化 中心擴展

3. 想好再下手 思考得多敲得少 邊敲邊想反而會耗費更多的時間

參考鏈接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647java-bao-li-dpzhong-xin-kuo-zhan-xiang-jie-by-u/
參考鏈接：鏈接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-fang-shi-qiu/
參考鏈接：https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/

總結

以上是生活随笔為你收集整理的[Leetcode][第647题][JAVA][回文子串][动态规划][中心扩展][Manacher 算法]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。