647.回文子串

/*
 * @lc app=leetcode.cn id=647 lang=typescript
 *
 * [647] 回文子串
 * dp[i,j] = s[i]===s[j] && (j-i<=2 || dp[i+1][j-1])
 */

// @lc code=start
function countSubstrings(s: string): number {
	let len = s.length;
	let dp: boolean[][] = Array.from({ length: len }, () =>
		Array(len).fill(false)
	);
	let res: number = 0;
	for (let i = len - 1; i >= 0; --i) {
		for (let j = i; j < len; ++j) {
			dp[i][j] = s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1]);
			if (dp[i][j]) {
				res++;
			}
		}
	}
	return res;
}

console.log(countSubstrings("abc"));

// @lc code=end