1003. 检查替换后的词是否有效.md

一、替换

根据题意进行反向模拟,每次替换掉 "abc" 即可 同时记录是否替换成功

代码

class Solution {
    public boolean isValid(String s) {
        boolean h = true;
        while (h) {
            String t = s.replaceAll("abc", "");
            if (t.length() == s.length()) h = false;
            else s = t;
        }
        return s.length() == 0;
    }
}

二、利用栈结构

根据题意,有效字符串第一个 'c' 必定连接在 "ab" 后方 从头开始遍历字符串 用栈来记录已经出现的 'a' 和 'b' 当遍历到 'b' 时检查栈首是否为 'a' 当遍历到 'c' 时检查栈首是否为 'b' 并出栈 接着再检查栈首是否为 'a' 同时出栈

代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case 'a':
                    stack.add(c);
                    break;
                case 'b':
                    if (!stack.isEmpty() && stack.peek() == 'a') stack.add(c);
                    else return false;
                    break;
                default:
                    if (!(stack.size() >= 2 && stack.pop() == 'b' && stack.pop() == 'a')) return false;
            }
        }
        return stack.isEmpty();
    }
}

优化

Java的Stack效率较低 可以使用链表代替栈

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> list = new LinkedList<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case 'a':
                    list.addLast(c);
                    break;
                case 'b':
                    if (!list.isEmpty() && list.getLast() == 'a') list.addLast(c);
                    else return false;
                    break;
                default:
                    if (!(list.size() >= 2 && list.removeLast() == 'b' && list.removeLast() == 'a')) return false;
            }
        }
        return list.isEmpty();
    }
}

还是不够快 因为栈需要的最大长度是确定的 所以可以用数组代替 效率直接拉满

class Solution {
    public boolean isValid(String s) {
        char[] cs = new char[s.length() + 2];
        int i = 2;
        for (char c : s.toCharArray()) {
            if (c == 'a') cs[i++] = c;
            else if (c == 'b') {
                if (cs[i - 1] != 'a') return false;
                cs[i++] = c;
            } else {
                if (cs[i - 1] != 'b' || cs[i - 2] != 'a') return false;
                i -= 2;
            }
        }
        return i == 2;
    }
}

感谢您看到这里 喜欢的话不妨点个赞吧 您的点赞是我创作的动力