LeetCode(Others)Valid Parentheses

2018-06-19

Valid Parentheses

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1 2	Input: "()" Output: true

Example 2:

1 2	Input: "()[]{}" Output: true

Example 3:

1 2	Input: "(]" Output: false

Example 4:

1 2	Input: "([)]" Output: false

Example 5:

1 2	Input: "{[]}" Output: true

思路：首先想到字符串长度为奇数时肯定返回false。我自己想出的算法里用到了递归，先利用一个for循环找到第一个为左边括号的字符，即”(“ ,”[“和”{“，然后再向后边找那个为对应闭括号的字符，如果该字符正好位于字符串的最后一个字符，则再判断去掉对应括号头尾后的子字符串是否合法，如果合法，就说明该字符串是合法的。

代码如下：

class Solution {
    public boolean isValid(String s) {
    if(s.length()==0){
            return true;
        }
        int len=s.length();
        if(len%2==1){
            return false;
        }
        if(s.charAt(0)==']' || s.charAt(0)=='}' || s.charAt(0)==')' ) {
        	return false;
        }
        for(int i=0;i<len;i++){
           if(s.charAt(i)=='('){
               for(int j=i+1;j<len;j++){
                   if(s.charAt(j)==')'){
                       String temp=new String(s.substring(i+1,j));
                       if(isValid(temp) && j==len-1){
                    	   return true;
                       }
                   }
               }
           }
            
           if(s.charAt(i)=='['){
               for(int j=i+1;j<len;j++){
                   if(s.charAt(j)==']'){
                       String temp=new String(s.substring(i+1,j));
                       if(isValid(temp) && j==len-1){
                    	   return true;
                       }
                   }
               }
           }
            
           if(s.charAt(i)=='{'){
               for(int j=i+1;j<len;j++){
                   if(s.charAt(j)=='}'){
                       String temp=new String(s.substring(i+1,j));
                       if(isValid(temp) && j==len-1){
                    	   return true;
                       }
                   }
               }
           }
        }
        
        return false;
    }
}

但是该算法不能通过LeetCode上的最后一个测试用例，超时，需要考虑复杂度更低的算法。

在leetcode的论坛上发现一个很有趣的解法，通过直接操作字符串，删除其中成对的括号，如果删除全部成对括号后最后字符串的长度为0，则说明是有效的字符串。该算法也能通过，但是在效率不高，思想很有趣。

代码如下：

class Solution {
    public boolean isValid(String s) {
        int len;
        do{
            len=s.length();
            s=s.replace("{}","").replace("[]","").replace("()","");
        }while(s.length()!=len);
        
        return s.length()==0;
    }
}