LeetCode 解答 #32. Longest Valid Parentheses プログラミング練習

問題：

難易度:　hard
入力:　文字列s
目的: 入力の中で最長な有効な括弧群の長さを返せ
出力:　int

前に有効括弧群の判断をする問題がありましたが、今回はその延長問題です。
括弧群の有効については問題♯20問目を参考にしてください。
stlisacity.hatenablog.com

注意すべき事:　

• 括弧は（）の組み合わせで初めて有効になる

• 有効な括弧群は入力の中に複数存在するケースがある

以下回答です。

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int res = 0;
        for (int i=0; i<s.length(); i++) {
            if (stack.isEmpty() && s.charAt(i) != ')') {
                stack.push(i);
            }
            else if (stack.isEmpty() && s.charAt(i) == ')') {
                res = Math.max(res, i-start);
                start = i+1;
                stack.clear();
            }
            else if (s.charAt(i) == ')' && s.charAt(stack.peek()) == '(') {
                stack.pop();
            }
            else if (s.charAt(i) == '(') {
                stack.push(i);
            }
        }
        int over = s.length();
        while (!stack.isEmpty()) {
            int temp = stack.pop();
            res = Math.max(res, over - temp - 1);
            over = temp;
        }
        res = Math.max(res, over - start);
        return res;
    }
}

♯20同様、stackを使った回答です。
forで入力を読み込み、(で始まる場合stackにpush
)の前に(がスタックにある場合有効ペアなので前の(をpopし次に進む
無効だった場合は現在の長さを記録し、stackを空にし繰り返す。

さて文字列の中の文字をすべて読み終えた時、
もしスタックが空でしたら最後の括弧群が有効だと言うことになります。
しかしスタックに文字が残っている場合、
”()(((()”、　'()()()(()()"
等の可能性があります。
無効とは判断されていないが、
未完成の括弧群です。
その場合、有効部分を切り離し長さを比べる必要があります。
すべての有効部分を比べ、一番大きい長さを返せば回答完了です。

今日は以上。
よいプログラミング生活を！