Java Concise O(n^2) Time O(1) Space DP Solution


  • 1
    public int countSubstrings(String s) {
        int count = 0; 
        for (int i=0;i<s.length();i++) count += getCount(s, i, 0) + getCount(s, s.length() - 1, i + 1);
        return count;
    }
    
    public int getCount(String s, int l, int r) {
        int count = 0;
        while (l >= 0 && r < s.length()) {
          if (l >= r || s.charAt(l) == s.charAt(r)) count += l-- <= r++ ? 1 : 0;
          else break;
        }        
        return count;
    }
    

  • 1
    Y

    The count method can be more concise

        public int countSubstrings(String s) {
            char[] ss = s.toCharArray();
            int count = 0;
            for (int i = 0; i < s.length(); i++) {
                count += count(ss, i, i);
                count += count(ss, i, i + 1);
            }
            return count;
        }
        
        int count(char[] s, int l, int h) {
            int count = 0;
            for (; l >=0 && h < s.length && s[l] == s[h]; l--, h++, count++);
            return count;
        }
    

Log in to reply
 

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