DP- O(n2) , Java simple solution !!


  • 0
    S

    public class Solution {
    public int countSubstrings(String s) {
    if(s==null ||s.length()==0) return 0;
    int count=0;
    boolean[][] flag= new boolean[s.length()][s.length()];
    for(int len=1;len<=s.length();len++){
    for(int i=0;i+len<=s.length();i++){
    int j=i+len-1;
    if(s.charAt(i)==s.charAt(j)){
    if(j-i<2 || flag[i+1][j-1]){
    flag[i][j]=true;
    count++;
    }
    }
    }

        }
      return count;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.