Java verbose O(N) time O(1) space on DP/recursion inspired by Palindromic Substrings


  • 0

    This is a solution inspired by one solution for the problem Palindromic Substrings. I personally refer to them all as Substring Counting problems. Good performance, verbose code but easy to understand.

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            int res = 0, n = A.length, i = 0;
            if (n < 3)
                return 0;
            while (i < n) {
                int end = extendRun(A, i);
                int length = end - i + 1;
                i = end;
                res += countSlices(length);
            }
            return res;
        }
    
        public int extendRun(int[] A, int start) {
            int n = A.length;
            if (start + 2 >= n)
                return start + 1;
            int diff = A[start + 1] - A[start];
            int curr = start + 1;
            while (curr + 1 < n && A[curr + 1] - A[curr] == diff)
                curr++;
            return curr;
        }
    
        public int countSlices(int length) {
            if (length < 3)
                return 0;
            // use formula rather than directly count
            int N = length - (3 - 1);
            return N * (N + 1) / 2;
        }
    }
    

    Explanation by example:
    for the example 1,1,2,3,4,5,6,5,4,3, we find at [1]the longest slice 1,2,3,4,5,6 of length 6. We can calculate the number of slices in it with the countSlices method. Then we restart the extending from the position of 6, and found 6,5,4,3. Again, count.

    The countSlices method can also be implemented like:

        public int countSlices(int length) {
            if (length < 3) return 0;
            int sum = 0;
            for (int i = length; i >= 3; i--) 
                sum += length - (i - 1);
            return sum;
        }
    

    Per my own submissions, the two ways of implementing this method does not make a noticeable difference in OJ feedback.


Log in to reply
 

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