32. Longest Valid Parentheses (Hard)

https://leetcode.com/problems/longest-valid-parentheses/

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Solutions

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();

        // Keep the track of ith char whether s.char[i] is part of a valid parenthese pair or not.
        boolean[] track = new boolean[s.length()];
        Arrays.fill(track, false);

        // sort out all the valid parenthese pairs
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            }

            // if s.charAt(index) matches s.char(i) and for a valid pair, set both track[i]
            // and track[index] true
            if (s.charAt(i) == ')' && !stack.isEmpty()) {
                int j = stack.pop();
                track[i] = true;
                track[j] = true;
            }
        }

        int max = 0;

        // sort out the consecutive elements that are able to form valid parentheses pairs
        int count = 0;
        for (int i = 0; i < track.length; i++) {
            if (track[i]) {
                count++;
            } else {
                max = Math.max(max, count);
                count = 0;
            }
        }

        return Math.max(max, count);
    }
}

Incorrect Solutions

class Solution {

    // TODO Incorrect solution

    // "()(()" expected 2, output 4

    // The key idea of solving this problem is using stack

    public int longestValidParentheses(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }

        Stack<Character> stack = new Stack<>();

        int max = 0;
        int count = 0;


        int len = s.length();
        for (int i = 0; i < len; i++) {
            // if it is open parenthese, push into stack
            if (s.charAt(i) == '(') {
                stack.push('(');
                continue;
            }

            // if the ith char is ')' and stack is not empty, we can form a valid pair of parenthese
            if (s.charAt(i) == ')' && !stack.isEmpty()) {
                stack.pop();
                count += 2;

                max = Math.max(count, max);
            }
            // mal-formed
            else if (s.charAt(i) == ')' && stack.isEmpty()) {
                count = 0;
                stack.clear();
            }
        }

        return max;
    }
}

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""