Leetcode 20题
题目描述：
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]'的字符串 s ，判断字符串是否有效。有效字符串需满足：
1）左括号必须用相同类型的右括号闭合。
2）左括号必须以正确的顺序闭合。
解题思路：
1）将字符串中的‘()’替换为‘’，‘[]’替换为‘’,’{}'替换为；‘’, 替换完之后字符串的长度若为0，则返回true，若不等于0，则返回false
class Solution {
public boolean isValid(String s) {
int length = s.length()/2;
for (int i = 0; i < length; i++) {
s = s.replace("()","").replace("[]","").replace("{}","");
}
return s.length() == 0;
}
}
2）利用栈遍历字符串的字符。在遍历的过程中，若栈为空或者没有我们要匹配的字符，则返回false
class Solution01{
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == '{') stack.push('}');
else if (stack.isEmpty() || c!=stack.pop()) return false;
}
return stack.isEmpty();
}
}
验证过程：
package no20;
import java.util.Stack;
//给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
class Solution {
public boolean isValid(String s) {
int length = s.length()/2;
for (int i = 0; i < length; i++) {
s = s.replace("()","").replace("[]","").replace("{}","");
}
return s.length() == 0;
}
}
class Solution01{
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == '{') stack.push('}');
else if (stack.isEmpty() || c!=stack.pop()) return false;
}
return stack.isEmpty();
}
}
public class No20 {
public static void main(String[] args) {
Solution01 solution = new Solution01();
boolean a = solution.isValid(new String("()[]{}"));
System.out.println(a);
}
}