共计 1632 个字符，预计需要花费 5 分钟才能阅读完成。
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 * 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)
正文完
