[Java/C++] 6 lines solution - NO DP


  • 12

    The idea is count the number of different palindromic substrings from their respective middle.

    In the following code, when we consider the substring s[i-j, ..., i+j], i is the middle index of the substring; When we consider the substring s[i-1-j, ..., i+j], (i-1, i) is the middle index of the substring.

    C++ version:

        int countSubstrings(string s) {
            int res = 0, n = s.length();
            for(int i = 0; i < n; i++){
                for(int j = 0; i-j >= 0 && i+j < n && s[i-j] == s[i+j]; j++)res++; //substring s[i-j, ..., i+j]
                for(int j = 0; i-1-j >= 0 && i+j < n && s[i-1-j] == s[i+j]; j++)res++; //substring s[i-1-j, ..., i+j]
            }
            return res;
        }
    
    

    Java version:

        public int countSubstrings(String s) {
            int res = 0, n = s.length();
            for(int i = 0; i<n ;i++ ){
                for(int j = 0; i-j >= 0 && i+j < n && s.charAt(i-j) == s.charAt(i+j); j++)res++; //substring s[i-j, ..., i+j]
                for(int j = 0; i-1-j >= 0 && i+j < n && s.charAt(i-1-j) == s.charAt(i+j); j++)res++; //substring s[i-1-j, ..., i+j]
            }
            return res;
        }
    

  • 0

    Hope your advice!


  • 0
    L

    Interesting way to do it. Nice piece of code.


  • 0
    L

    @Vincent-Cai Is your solution a O(N^2) solution? I am not sure about that.


  • 0

    @laro Yes, it is.


Log in to reply
 

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