题目描述: 给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
示例1: 输入:s = “()” 输出:true
示例2: 输入:s = “()[]{}” 输出:true
示例3: 输入:s = “(]” 输出:false
示例4: 输入:s=“({[]})” 输出:true
题目分析: 题目中所说的有效括号仅指字面意义上的有效,即不考虑数学意义上括号的意义:也就是说,只要括号正确闭合就行,类似 ([])、({})、[{}]、([{}]) 等也符合题目中有效括号的定义。例如示例4输出为true
思路1: 对于任何有效的初始括号字符串均至少含有()、{}、[]三对括号中的一对,故使用contains()循环判断是否含有这三对括号,若有则使用replace()删除,最终有效字符串会删减为空串,将最终的字符串使用equals(“”)比较,为空串则有效,反之无效。 该思路是我自己解题的思路,但由于在循环内调用函数,导致时间复杂度和空间复杂度高,性能差,代码见下方
解题步骤如下: 1、whie循环,以字符串是否含有()、[]、{}三对括号为循环条件 2、while循环内,以空字符“”替换字符串中的()、[]、{} 3、循环以字符串内不含有三对括号结束 4、判断最终字符串是否为空串,为空则true,反之为false
思路2: 使用栈,利用stack的后进先出的特性,遍历括号字符串。 若字符串以(、[、{开头,且从左至右遍历过程中,遇到(、[、{则向stack栈中压入对应的右括号,遇到)、]、}则弹出栈顶元素并与当前字符比较,相同则继续,不同则结束返回false。 若字符串以)、]、}三者之一开头,则为无效字符串,以栈空为条件结束返回false 该思路借鉴了他人的题解,很强大
解题步骤 1、声明一个空栈 2、使用toCharArray()将字符串转为字符数组,并在for循环中遍历 3、循环内:若该字符对应(、[、{则向栈中压入对应的右括号;反之则弹出栈顶元素并判断是否与当前字符相同且栈是否为空栈。若为空栈或与栈顶元素不同,则返回false 4、循环结束后,判断栈是否为空,为空则有效;反之无效。
//思路1代码如下
//时间空间耗费高
public boolean isValid(String s) {
while (s.contains("{}") || s.contains("()") || s.contains("[]")) {
s = s.replace("()", "");
s = s.replace("{}", "");
s = s.replace("[]", "");
}
if (!s.equals("")) {
return false;
} else {
return true;
}
}
//思路2代码如下
//改进,借鉴了他人思路
public boolean isValid2(String s) {
Stack<Character>stack = new Stack<Character>();
for(char ch :s.toCharArray())
{
if(ch == '(')
stack.push(')');
else if (ch == '[')
stack.push(']');
else if(ch == '{')
stack.push('}');
else if(stack.isEmpty()||ch != stack.pop())
return false;
}
return stack.isEmpty();
}
该题总共提交了五次化,花费了挺多时间,前四次依照自己的解题思路,前三次出错,第四次成功但占用时间空间多,第五次为借鉴他人思路优化解题。 第一次解题:只考虑了括号的数量成对,未考虑括号的位置 第二次解题:想的太多,认为{}的包含关系是固定的,即[{}] 为无效括号 第三次解题:对于空字符串的判断使用!=null 而不是equals()导致错误 第四次解题:成功运行,但时间空间占用多,如下图所示
第五次解题:借鉴他人思路,使用栈优化代码,结果如下所示。