Q22 Palindromic Substrings - LeetCode 647
Fri Mar 24 2023 09:11:36 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int countSubstrings(String s) {
/* question of DP gap strategy vid 32 of dp playlist
1)making a boolean array for checking pallindrome by keeping start
points on coloumn and end points on rows
2)travelling the upper triangle only ,where 0th diagnol represents
substring with 0 gap that is that element itself
3) handling for 0 ,1 gap which are trivial case then handling for
2 onwards , where we will check extremities and if inside string is
also pallindrome by checking diagnolly behind
*/
//1
boolean dp[][] = new boolean[s.length()][s.length()];
int count = 0 , n = s.length();
//2
for(int gap = 0 ; gap < n ; gap ++){
//every diagnol ends at last coloumn,so this loop runs from first
//row till last coloumn
for(int i = 0 , j = gap ; j < n ; i++ , j++){
//handling for 0 gap diagnol -> all are true
if(gap == 0 ){
dp[i][j] = true;
count++;
}
//handling for 1 gap diagnol -> check if both chars are equal
else if(gap == 1){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = true;
count++;
}
}
//3
else{
if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true){
dp[i][j] = true;
count++;
}
}
}
}
return count;
}
}
content_copyCOPY
https://leetcode.com/problems/palindromic-substrings/
Comments