关于算法:每日一题检查替换后的词是否有效

关键词：字符串匹配

题目起源：1003. 查看替换后的词是否无效 – 力扣（Leetcode）

给你一个字符串 s，请你判断它是否无效。

字符串 s 无效须要满足：假如开始有一个空字符串 t = ""，你能够执行 任意次 下述操作将 t 转换为 s：

将字符串 "abc" 插入到 t 中的任意地位。模式上，t 变为 tleft + "abc" + tright，其中 t == tleft + tright。留神，tleft 和 tright 可能为空。

如果字符串 s 无效，则返回 true；否则，返回 false。

输出：s = "aabcbc"
输入：true
解释：""->"abc"->"aabcbc"因而，"aabcbc" 无效。

输出：s = "abcabcababcc"
输入：true
解释：""->"abc"->"abcabc"->"abcabcabc"->"abcabcababcc"因而，"abcabcababcc" 无效。

输出：s = "abccba"
输入：false
解释：执行操作无奈失去 "abccba"。

数据范畴
1 <= s.length <= 2 * 104
s 由字母 'a'、'b' 和 'c' 组成

本题与括号匹配（20. 无效的括号 – 力扣（Leetcode））相似，可应用栈来求解。

具体做法如下：

遇到字符 a：间接入栈
遇到字符 b：若栈顶不为字符 a，返回false，否则入栈
遇到字符 c：若栈顶不为字符 b，返回false，否则阐明找到一个匹配的abc，出栈 2 次（将 b 和 a 出栈）

操作合并（设栈顶元素为 top，以后字符为 cur）：

当 cur 为字符 b 或 c 时，若 top!=cur-1，返回false，否则，作如下思考：

通过后面的剖析可知，遇到字符 c 时，间接出栈两次，也行将与之匹配的 b 和 a 出栈，对于出栈的字符 b，咱们通过判断确定其的确是字符 b，而对于出栈的字符 a，是因为咱们能必定字符 b 的后面必然有一个字符 a，所以没进行判断，于是，无妨让这个字符 a 在遇到字符 b 时就间接出栈，这样咱们遇到字符 c 时，只须要出栈 1 次。

通过剖析，遇到字符 c 时的 2 次出栈等价于遇到字符 b 出栈 1 次（将 a 出栈）、遇到字符 c 出栈 1 次（将 b 出栈），也即，当 cur 为字符 b 或 c 时，间接出栈 1 次即可。
当 cur 为字符 a 或 b 时，间接入栈。当 cur 为字符 b 时，后面曾经实现判 false 和出栈的操作，还有将字符 b 自身入栈的操作没有实现，所以还须要将字符 b 入栈。当 cur 为字符 a 时，后面没有解决过为字符 a 的状况，所以这里还须要将字符 a 入栈。

因为遍历指针总是处于栈顶之后（或者处于雷同地位），所以可原地进行操作。

奢侈写法

bool isValid(string s) {
    // 栈顶元素所在位置
    int i = -1;
    // 栈
    for (char c: s) {
        // a：间接入栈
        if (c == 'a')s[++i] = c;
            // b：栈顶必须为 a
        else if (c == 'b') {if (i == -1 || s[i] != 'a')return false;
            s[++i] = c;
        }
            // c：栈顶必须为 b
        else {if (i == -1 || s[i] != 'b')return false;
            i -= 2;     // 出栈
        }
    }
    return i == -1;
}

工夫复杂度：O(n)

空间复杂度：O(1)

操作合并

bool isValid(string s) {
    // 栈顶元素所在位置
    int i = -1;
    // 栈
    for (char c: s) {
        /**
         * b/c：栈顶必须为 a /b
         *      如果以后字符为 b 或 c，则此处相当于执行一次出栈操作
         *      以后字符为 b 时，将栈顶的 a 出栈了，后续遇到与之匹配的 c 时，只须要将以后的 b 出栈即可
         *      以后字符为 c 时，将栈顶的 b 出栈了，以后的 c 即为下面所说的“遇到与之匹配的 c”，因为与
         * 之匹配的 a 曾经出栈，所以只有不把这个 a 出栈，就相当于把整个匹配的 abc 出栈了
         */
        if (c > 'a' && (i == -1 || c - s[i--] != 1))return false;
        /**
         * a/b：入栈
         */
        if (c < 'c')s[++i] = c;
    }
    return i == -1;
}

工夫复杂度：O(n)

空间复杂度：O(1)

关于算法:每日一题检查替换后的词是否有效

1003. 查看替换后的词是否无效

题目形容

问题剖析

代码实现