Question Link

https://leetcode.com/problems/palindromic-substrings/

Question Description

Given a String s, return the number of palindromic substrings in it.
Input: s= abbac

Simulation

Solution 1: Two Pointers

Check every character, and expand them until reach boundary

Solution 2: Two Pointers + DP

DP(i,j) represent if a substring s within the range [i,j] is a palindrome or not.
Case 1: I
If i>j, then DP(i,j) = False. j should always larger than i as this is what we defined in range
If i==j, then DP(i,j) = True. Each single letter is considered as a palindrome
If iif s.charAt(i) !=s.charAt(j), DP(i,j)= False
if s.charAt(i) == s.charAt(j), then DP(i,j)= DP(i+1,j-1) || i+1>=j-1

Traverse Order
Main Diagonal: T T T T T
Sub Diagonal: F T F F
Sub Diagonal: F F F
Sub Diagonal: T F
Sub Diagonal: F

Implementation

Solution 1: Two Pointers

public int countSubstrings(String s) {
    var count = 0;
    for (var i = 0; i < s.length(); i++)
        count += countSubstrings(s, i, i) + countSubstrings(s, i, i + 1);
    return count;
}
private int countSubstrings(String s, int start, int end) {
    var count = 0;
    while (start >= 0 && end < s.length() && s.charAt(start--) == s.charAt(end++)) 
        count++;
    return count;
}

Solution 2: DP