package Classify.DP.Medium;
import org.junit.jupiter.api.Test;
public class PalindromicSubstrings {
/**
* 基本思路：這里的 dp 方程的每一個元素就代表我要以當(dāng)前元素作為回文子串的結(jié)尾時候的回文子串的數(shù)量
* 那么遞推公式就是以上一個元素結(jié)尾時候的子串?dāng)?shù)量加上本次的結(jié)尾的子串的數(shù)量就能獲得總數(shù)量了
* 而判斷當(dāng)前結(jié)尾的回文子串就是判斷到對稱的元素，然后翻轉(zhuǎn)操作做判斷即可
* @param s
* @return
*/
public int countSubstrings(String s) {
int[] dp = new int[s.length()];
dp[0] = 1;
for (int i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1] + currentCount(s, i);
}
return dp[s.length() - 1];
}
private int currentCount(String string, int i) {
int count = 0;
for (int j = i; j >= 0; --j) {
if (string.charAt(i) != string.charAt(j)) {
continue;
}
if (new StringBuilder(string.substring(j, i + 1)).reverse().toString().equals(string.substring(j, i + 1))) {
++count;
}
}
return count;
}
@Test
public void fun() {
System.out.println(countSubstrings("aaa"));
}
}
