持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第14天，点击查看活动详情
题：给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号
(必须有相应的右括号)。 - 任何右括号
)必须有相应的左括号(。 - 左括号
(必须在对应的右括号之前)。 *可以被视为单个右括号)，或单个左括号(，或一个空字符串。- 一个空字符串也被视为有效字符串。
示例 1:
代码语言：javascript复制输入: "()"
输出: True示例 2:
代码语言：javascript复制输入: "(*)"
输出: True示例 3:
代码语言：javascript复制输入: "(*))"
输出: True注意:
- 字符串大小将在 [1，100] 范围内。
思路
看到匹配括号的，首先想到的是用栈模拟匹配，常规没有*符号情况下，代码可以这样写：
public static boolean checkValidString(String s) {
LinkedList<Integer> stack = new LinkedList<>();
char[] chars = s.toCharArray();
int n = s.length(), i;
for (i = 0; i < n; i ) {
if (chars[i] == '(') {
stack.offerLast(i);
} else if (chars[i] == ')') {
if (!stack.isEmpty()) {
stack.removeLast();
} else {
return false;
}
}
}
return stack.isEmpty();
}字符串中增加了*号，可以变换成( 、) 以及空格，这样一个栈肯定是不行了。增加一个栈来记录*号呢？
计算过程为：
- 如果遇到左括号，则将当前下标存入左括号栈。
- 如果遇到星号，则将当前下标存入星号栈。
- 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配：
- 如果左括号栈不为空，则从左括号栈弹出栈顶元素；
- 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素；
- 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回 false。
最后如果stackA 和 stackB 还有剩余，再根据符号下标进行比较：
- 左括号下标大于星号下标，返回false
具体过程请看代码
代码语言：javascript复制public static boolean checkValidString(String s) {
// 记录（下标
LinkedList<Integer> stackA = new LinkedList<>();
// 记录*下标
LinkedList<Integer> stackB = new LinkedList<>();
char[] chars = s.toCharArray();
int n = s.length(), i;
for (i = 0; i < n; i ) {
if (chars[i] == '(') {
// 记录下（下标
stackA.offerLast(i);
} else if (chars[i] == '*') {
// 记录下*下标
stackB.offerLast(i);
} else if (chars[i] == ')') {
// 优先于（进行匹配，没有（则与*匹配，两者都没有说明不能匹配
if (!stackA.isEmpty()) {
stackA.removeLast();
} else if (!stackB.isEmpty()) {
stackB.removeLast();
} else {
return false;
}
}
}
while (!stackA.isEmpty() && !stackB.isEmpty()) {
Integer a = stackA.removeLast();
Integer b = stackB.removeLast();
// 如果（在*前，不能匹配
if (a > b) {
return false;
}
}
// 最后根据（的情况进行判断，有剩余则说明存在（不能被匹配
return stackA.isEmpty();
}
