Fork me on GitHub

Palindromic Substrings

Posted on

Descrpition

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

Solution (O(n^2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0; 
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for(int i = 0; i < s.length(); i++) { dp[i][i] = true; count += 1; }
        for(int i = 0; i < s.length() - 1; i++) if(s.charAt(i) == s.charAt(i+1) ) { dp[i][i+1] = true; count += 1; }
        for(int lens = 3; lens <= s.length(); lens++) {
            for(int left = 0; left <= s.length() - lens; left++) {
                int right = left + lens - 1;
                if (dp[left + 1][right - 1] && s.charAt(left) == s.charAt(right) ){
                    dp[left][right] = true;
                    count += 1;
                }
            }
        }
        return count;
    }
}

hash with Dichotomy(O(N*logN))

No result yet