1003. 查看替换后的词是否无效
关键词：字符串匹配
题目起源：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 * 104s 由字母 '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)