Longest Valid Parentheses (H)

題目

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: 2
Explanation: The longest valid parentheses substring is "()"

題意

給定一個只包含左右括號的字串，輸出連續匹配括號對的最長長度，

思路

個人想到的方法是壓堆疊法：建兩個堆疊，一個par存括號字符，另一個index存括號字符對應的下標，用i遍歷字串，如果為'('，則同時壓入兩個堆疊；若為')'，此時如果par為空，則壓入par和index，如果par非空且堆疊頂元素為'('，說明配對成功，同時出堆疊par和index，而此時index的堆疊頂元素(非空時)代表的是當前最右邊無法匹配的括號的下標，那么 i - index.peek() (index非空)/ i + 1 (index為空) 就代表了新增一對匹配括號對后更新的連續匹配長度，將之與max比較并更新max，
官方的壓堆疊法解答只使用了一個堆疊，但整體思路是一樣的，

左右掃描法：設兩個計數器left和right，先從左向右掃描字串，'('則left+1，')'則right+1，每掃描一個字串，比較left和right，如果left < right，則將left和right重置，如果left == right，則更新max；同理再從右向左掃描，如果left > right，則將left和right重置，如果left == right，則更新max，
這是因為左右掃描，不能正確處理"( ) ( ( ( ) )"這種情況，而右左掃描可以；右左掃描不能正確處理"( ( ) ) ) ( )"這種情況，但左右掃描可以，

動態規劃：dp陣列記錄以當前括號字符為結尾的最大有效長度，顯而易見只有以')'為結尾才可能形成有效字串，因此只有在當前字符為')'時才進行處理，共可能會有以下兩種情況：

1. s[i] == ')' && s[i - 1] == '('，這時很容易得到 \(dp[i] = dp[i - 2] + 2\)；
2. s[i] == ')' && s[i - 1] == ')'，這種情況下，先找到以s[i - 1]為結尾的有效字串開頭的前一個字符c (當然如果dp[i - 1] == 0，就不需要找這個c了)，如果c為'('，則與s[i]構成匹配括號對，同時還要考慮以c前一個字符c'為結尾的有效字串的長度 (舉個例子，"( ) ( ( ) )"，最后一個')'為s[i])，最終得到 \(dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]\)，

代碼實作

Java

壓堆疊法

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;

        Deque<Character> par = new ArrayDeque<>();
        Deque<Integer> index = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                par.push(c);
                index.push(i);
            } else {
                if (par.isEmpty() || par.peek() != '(') {
                    par.push(c);
                    index.push(i);
                } else {
                    par.pop();
                    index.pop();
                    max = Math.max(max, index.isEmpty() ? i + 1 : i - index.peek());
                }
            }
        }

        return max;
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                // 出堆疊后若堆疊空，說明出堆疊的是不匹配的')'，將當前')'壓入堆疊
                // 若堆疊非空，說明出堆疊的是匹配的'('，更新max
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        
        return max;
    }
}

左右掃描法

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        int left = 0, right = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                max = Math.max(max, left + right);
            } else if (left < right) {
                left = right = 0;
            }
        }

        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                max = Math.max(max, left + right);
            } else if (left > right) {
                left = right = 0;
            }
        }
        
        return max;
    }
}

動態規劃

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;

        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                } else {
                    if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                    }
                }
            }
        }
        
        for (int i = 0; i < s.length(); i++) {
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

JavaScript

壓堆疊法

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let max = 0
  let stack = []
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(' || stack.length === 0 || s[stack[stack.length - 1]] === ')') {
      stack.push(i)
    } else {
      stack.pop()
      max = Math.max(max, i - (stack.length === 0 ? -1 : stack[stack.length - 1]))
    }
  }
  return max
}

左右掃描法

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  return Math.max(scan(s.split(''), true), scan(s.split('').reverse(), false))
}

let scan = function (s, flag) {
  let left = 0, right = 0
  let max = 0
  for (let p of s) {
    if (p === '(') {
      left++
    } else {
      right++
    }
    if (left === right) {
      max = Math.max(max, left + right)
    } else if (flag ? left < right : left > right) {
      left = right = 0
    }
  }
  return max
}

動態規劃

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let max = 0
  let dp = new Array(s.length).fill(0)

  for (let i = 1; i < s.length; i++) {
    if (s[i] === ')') {
      if (s[i - 1] === '(') {
        dp[i] = i > 1 ? dp[i - 2] + 2 : 2
      } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0)
      }
      max = Math.max(max, dp[i])
    }
  }

  return max
}

標籤：其他

上一篇：0031. Next Permutation (M)

下一篇：vlan間互通的奇怪問題。