算法笔试题：有效的括号字符串，常规栈思路

题：给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(\*)"
输出: True

示例 3:

输入: "(\*))"
输出: True

注意:

1. 字符串大小将在 [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();
}

字符串中增加了*号，可以变换成( 、) 以及空格，这样一个栈肯定是不行了。增加一个栈来记录*号呢？

计算过程为：

1. 如果遇到左括号，则将当前下标存入左括号栈。
2. 如果遇到星号，则将当前下标存入星号栈。
3. 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配：
   • 如果左括号栈不为空，则从左括号栈弹出栈顶元素；
   • 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素；
   • 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回 false。

最后如果stackA 和 stackB 还有剩余，再根据符号下标进行比较：

1. 左括号下标大于星号下标，返回false

具体过程请看代码

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();
}