【LeetCode】678.有效的括号字符串

欢迎来到李耶的频道【LeetCode面试题】。有效的括号字符串678.有效的括号字符串题目给定一个只包含三种字符的字符串()和*写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则任何左括号(必须有相应的右括号)。任何右括号)必须有相应的左括号(。左括号(必须在对应的右括号之前)。*可以被视为单个右括号)或单个左括号(或一个空字符串。一个空字符串也被视为有效字符串。输入: () 输出: True输入: (*) 输出: True输入: (*)) 输出: True输入: ((**) 输出: True 解释其中一个 * 可以是 )另一个可以是空字符串。输入: (((*) 输出: False提示字符串大小将在 [1, 100] 范围内。解法一贪心维护左括号数量范围思路维护一个可能的左括号数量范围[min, max]其中min表示最少可能的未匹配左括号数max表示最多可能的未匹配左括号数。遍历字符串根据当前字符调整范围。关键在于确保max始终非负最终min 0时有效。functioncheckValidString(s){letmin0;// 左括号数量的下界letmax0;// 左括号数量的上界for(constcharofs){if(char(){min;max;}elseif(char)){if(min0)min--;if(max--0)returnfalse;}else{// *if(min0)min--;// * 作为右括号max;// * 作为左括号}}returnmin0;}时间复杂度 / 空间复杂度O(n) / O(1)优势代码极其简洁一次遍历空间最优面试中最推荐的写法解法二双栈思路使用两个栈分别存储左括号和星号的下标。遍历字符串遇到左括号入left栈遇到星号入star栈遇到右括号优先用左括号匹配否则用星号匹配。遍历结束后将剩余的左括号与星号匹配要求星号在左括号的右边。functioncheckValidString(s){constleft[];conststar[];for(leti0;is.length;i){if(s[i](){left.push(i);}elseif(s[i]*){star.push(i);}else{// )if(left.length0){left.pop();}elseif(star.length0){star.pop();}else{returnfalse;}}}// 用星号匹配剩余的左括号while(left.length0star.length0){if(left.pop()star.pop()){returnfalse;// 星号在左括号左边无法匹配}}returnleft.length0;}时间复杂度 / 空间复杂度O(n) / O(n)优势思路直观与括号匹配的经典栈解法一脉相承解法三贪心区间边界思路维护一个「左括号数量」的区间[lo, hi]lo为可能的最小值hi为可能的最大值。遇到(则区间两端1遇到)则区间两端-1遇到*则lo--、hi。若hi 0则无效若lo 0则剪枝为 0。最终lo 0时有效。functioncheckValidString(s){letlo0;lethi0;for(constcharofs){if(char(){lo;hi;}elseif(char)){if(lo0)lo--;hi--;}else{// *if(lo0)lo--;hi;}if(hi0)returnfalse;loMath.max(lo,0);}returnlo0;}时间复杂度 / 空间复杂度O(n) / O(1)优势一次遍历空间最优与解法一异曲同工解法对比解法时间 / 空间复杂度优势推荐指数贪心数量范围O(n) / O(1)最简洁空间最优⭐⭐⭐⭐⭐区间边界O(n) / O(1)一次遍历逻辑清晰⭐⭐⭐⭐⭐双栈O(n) / O(n)经典栈思路易于理解⭐⭐⭐⭐扩展题有效的括号给定一个只包含括号的字符串判断是否有效。最长有效括号给定一个只包含(和)的字符串找出最长有效括号子串的长度。检查替换后的字符串是否有效给定一个只包含a、b、c的字符串判断是否可以通过不断插入abc得到。“天下事有难易乎为之则难者亦易矣不为则易者亦难矣。” —— 彭端淑《为学》关注李耶每天一道面试题一起卷起来