网站开源系统站长统计代码

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
 

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

解法

匹配括号有一个特性，先出现的左括号后匹配。也就是说，第一个出现的的右括号，它的前一个必然是和他匹配的。

利用这个特点，我们找到第一个右括号，然后找到它的前一个，如果和它匹配，那么就将这一对字符置换为’a‘字符。然后找到下一个右括号，然后从它前一个字符开始寻找，如果找到和它匹配且不是’a‘的字符，就返回false，如果它前面所有字符都不和它匹配，也返回false。如果最后全部匹配，就返回true。当然，如果全部字符都是左括号，也返回false。

   public boolean isrelation(char a,char b){if(a=='('&b==')')return true;if(a=='['&b==']')return true;if(a=='{'&b=='}')return true;return false;}public boolean isleft(char c){if(c==')')return true;if(c==']')return true;if(c=='}')return true;return false;}public boolean isright(char d){if(d=='(')return true;if(d=='[')return true;if(d=='{')return true;return false;}public boolean isValid(String s) {int n = s.length();if(n%2==1)//1，先判断整体是否为偶数return false;char[] str = s.toCharArray();if(isleft(str[0]))return false;//2在判断左括号或者右括号的数量是否相等  int l=0,r=0;//判断是否能匹配。for(int i=0;i<n;i++){if(isright(str[i]))r++;if(isleft(str[i])){l++;int j;for(j=i-1;j>=0;j--){if(str[j]=='a')continue;else if(isrelation(str[j],str[i])){str[i]='a';str[j]='a';break;}elsereturn false;//入股一个右括号向左找到的第一个括号不是与他匹配的，返回false}if(j<0)//如果一个右括号没有找到左括号匹配，返回falsereturn false;}  }if(r!=l)return false;return true;}