题目

• 概述：给定有效字符串"abc"，且在有效字符串中任意位置插入有效字符串仍为有效字符串，其它都是无效字符串，现在给你一个字符串，让你判断给定的字符串是否是有效字符串

• 输入：字符串，长度范围[1, 20000]

• 输入子项：'a'或'b'或'c'

• 输出：字符串有效返回true，否则返回false

• 出处：https://leetcode-cn.com/problems/check-if-word-is-valid-after-substitutions/

思路

• 由于需要存储字符串"abc"的片段信息，在之后需要的时候使用，所以考虑用栈实现

• 遍历给定的字符串：

  1. 'a' => 将'a'入栈
  2. 'b'：
     1. 栈为空 => 返回false
     2. 栈顶字符为'a' => 将栈顶字符替换为'b'
     3. 栈顶字符为'b' => 返回false
  3. 'c'：
     1. 栈为空 => 返回false
     2. 栈顶字符为'a' => 返回false
     3. 栈顶字符为'b' => 将栈顶元素弹出

• 最后栈为空则字符串有效，否则字符串无效

代码

class Solution {
    public boolean isValid(String S) {
        LinkedList<Character> stack = new LinkedList<>();
        for (char c : S.toCharArray()) {
            switch (c) {
                case 'a':
                    stack.push(c);
                    break;
                case 'b':
                    if (stack.isEmpty() || stack.peek() == 'b') {
                        return false;
                    }
                    stack.pop();
                    stack.push(c);
                    break;
                case 'c':
                    if (stack.isEmpty() || stack.peek() == 'a') {
                        return false;
                    }
                    stack.pop();
                    break;
            }
        }
        
        return stack.isEmpty();
    }
}