Java Two O(n^2) methods


  • 0

    DP solution with O(n^2) time and memory

        public int countSubstrings(String s) {
            int n = s.length(), count = 0;
            boolean[][] dp = new boolean[n][n];
            for (int len = 1; len <= n; len++) {
                for (int i = 0; i+len-1 < n; i++) {
                    int j = i+len-1;
                    dp[i][j] = s.charAt(i) == s.charAt(j) && (i >= j-1 || dp[i+1][j-1]);
                    if (dp[i][j]) count++;
                }
            }
            return count;
        }
    

    Count the number of palindrome using ith element as mid point or ith and i+1th element as mid point

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

Log in to reply
 

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