My DP O(n) in Java with explanation


  • 1
    Y

    This is my thought process:
    Let's define S(i) as the longest parentheses till the ith character in the string.
    Let's start from the end, for the last character char[n], should it include in the S(n) or not?
    If not include it, then S(n) = S(n-1)
    if include it, we should start from the nth element, go backward in the string to find the longest valid parentheses. let's define it as f(n)
    So the formula is like this
    S(n) = max(S(n-1), f(n))
    there is one case that the nth element is not valid, means it's not part of any valid parentheses. this formula still works. As the f(n) would be 0, and the S(n) = S(n-1), which means it should not be included, as we expected.

    Having this formula, we should calculate memorize the f(n) from the beginning.
    Then basically we just return the max(f(0), f(1).....f(n))

    The implementation below uses one stack and one array.

    public class Solution {
        public int longestValidParentheses(String s) {
            if( s == null || s.isEmpty()){
                
                return 0;
            }
            
            
            int[] array = new int[s.length()];
            Stack<Integer> stack = new Stack<Integer>();
            char[] c = s.toCharArray();
            
            //mark the valid parentheses in an array with help of a stack
            for(int i = 0; i < c.length; i++){
                if(c[i] == '('){
                    stack.push(i);
                    array[i] = 0;
                }else{
                    if(stack.isEmpty()){
                        array[i] = 0;
                    }else{
                        array[stack.pop()] = 1;
                        array[i] = 1;
                    }
                }
            }
            
            // form the f(n) and meanwhile find the max(f(n))
            int max = 0;
            for(int i = 1; i < c.length; i++){
                if(array[i] != 0){
                    array[i] = array[i-1] + 1;
                }
                
                if(max < array[i]){
                    max = array[i];
                }
            }
            return max;
        }
    }

Log in to reply
 

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