Share my java solution with stack and DP


  • 5
    D

    Stack:

        public int longestValidParentheses(String s) {
            Stack<Integer> st = new Stack<>();
            int max = 0;
            for(int i=0;i<s.length();i++){
                if(s.charAt(i)==')'&&!st.isEmpty()&&s.charAt(st.peek())=='('){
                    st.pop();
                    max = Math.max(max, i-((st.isEmpty())?-1:st.peek()));
                }
                else    st.push(i);
            }
            return max;
        }
    

    DP:

    public int longestValidParentheses(String s) {
        /*max[i] = j means subsequence index i-j is longest valid Parentheses*/
        int[] max = new int[s.length()+1];
        max[s.length()] = s.length();
        int sum = 0;
        for(int i=s.length()-1;i>=0;i--){
            if(max[i+1]!=i+1){
                if(max[i+1]+1<s.length()&&s.charAt(i)=='('&&s.charAt(max[i+1]+1)==')'){
                    max[i] = (max[i+1]+2<s.length()+1&&max[max[i+1]+2]!=max[i+1]+2)?max[max[i+1]+2]:max[i+1]+1;
                }
                else    max[i] = i;
            }
            else if(i+1<s.length()&&s.charAt(i+1)==')'&&s.charAt(i)=='('){
                max[i] = (i+2<s.length()+1&&max[i+2]!=i+2)?max[i+2]:i+1;
            }
            else    max[i] = i;
            sum = Math.max(sum, max[i]-i+1);
        }
        return (sum==1)?0:sum;
    }

  • 0
    S

    I really like your clear and elegant solution:
    But could you elaborate a bit more on this line please:
    max = Math.max(max, i - ((stack.isEmpty())? - 1:stack.peek()));
    I don't fully get it.
    Thanks!


  • 0
    D

    After pop(), it can be empty, which means that s.substring(0,i+1) is valid so we need i-(-1); if not empty, s.substring(st.peek(),i+1) will be valid.


  • 0
    S

    Great response! Thanks a lot!


Log in to reply
 

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