[Leetcode] Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

数据结构题，使用栈来进行判断，要注意检查栈空的情况。

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                stack.push(s.charAt(i));
            }
            else {
                if(stack.size() == 0) return false;
                if(s.charAt(i) == ')' && stack.pop() != '(') 
                    return false;
                if(s.charAt(i) == ']' && stack.pop() != '[')
                    return false;
                if(s.charAt(i) == '}' && stack.pop() != '{')
                    return false;
            }
        }
        if(stack.size() == 0)
            return true;
        else
            return false;
    }

今天在论坛上看到了一个变种，除了括号以外，还加入了一个元素X，能够匹配任意的括号，求问一个给定的输入是否是一个合法的括号匹配。这道题可以使用O(n^3)的dp来做，对于每一个dp[i][j], 当存在k使得 dp[i][k] == true 且 dp[k+1][j] == true的时候，那么dp[i][j] = true，然而还有一种匹配的形式就是nested形式的匹配，上面的是并列，nested就是套起来的那种，所以需要检查i, j与dp[i+1][j-1]。总而言之，这道题可以看做是word break和palindrome的综合。下面是我写的代码，测试了几组样例：

1. [X]X ----> TRUE
2. []{}[X]X -----> TRUE
3. [X]] -------> TRUE
4. []X)([} -------> FALSE
5. [ ------> FALSE
6. }{ -------> FALSE
7. X}{X ------->TRUE

希望大家提供更多的样例来验证程序的对错。

import java.util.*;

public class ValidParenteses {
 public static boolean isValid(String s) {
  int n = s.length();
  boolean[][] dp = new boolean[n][n];

  for(int i = n-1; i >= 0; i--) {
   for(int j = i; j < n; j++) {
    if(i == j) {
     dp[i][j] = false; // single character could not be valid
    }
    else if(j == i+1) {
     if(s.charAt(i) == 'X' || s.charAt(j) == 'X') 
      dp[i][j] = true;
     else {
      if(s.charAt(i) == '(' && s.charAt(j) == ')')
       dp[i][j] = true;
      else if(s.charAt(i) == '[' && s.charAt(j) == ']')
       dp[i][j] = true;
      else if(s.charAt(i) == '{' && s.charAt(j) == '}')
       dp[i][j] = true;
      else
       dp[i][j] = false;
     }
    }
    else {
     if(dp[i+1][j-1] == false)
      dp[i][j] = false;
     else {
      if(s.charAt(i) == 'X' || s.charAt(j) == 'X') 
       dp[i][j] = true;
      else {
       if(s.charAt(i) == '(' && s.charAt(j) == ')')
        dp[i][j] = true;
       else if(s.charAt(i) == '[' && s.charAt(j) == ']')
        dp[i][j] = true;
       else if(s.charAt(i) == '{' && s.charAt(j) == '}')
        dp[i][j] = true;
       else
        dp[i][j] = false;
      }
     }
     for(int k = i+1; k <= j-2; k++) {
      if(dp[i][k] == true && dp[k+1][j] == true) {
       dp[i][j] = true;
       break;
      }
     }
    }
   }
  }
  return dp[0][n-1];
 }

 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   System.out.println(isValid(scan.next()));
  }
 }
}