prep-coding/leetcode/CountSubString.java at master · tushar-sharma/prep-coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {

    public boolean isPalindromic(String s) {

        StringBuilder sb = new StringBuilder(s);

        return sb.toString().equals(sb.reverse().toString());
    }

    public int countSubstrings(String s) {

        if (s.length() == 1){
            return 1;
        }

        int count = 0;

        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int g = 0; g < s.length(); g++) {

            for (int i = 0; (i + g) < s.length() ; i++) {

                if  (g == 0){
                    dp[i][i + g] = true;
                }

                else if (g == 1){
                    dp[i][i + g] = s.charAt(i) == s.charAt(i + g );
                }

                else {
                    if (s.charAt(i) == s.charAt(i + g ) && dp[i + 1][i + g - 1] == true) {
                        dp[i][i + g] = true;

                    }
                }

                if (dp[i][i + g] == true){
                    count++;
                }

            }
        }

        return count;

    }
}