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 问题分析
本题与括号匹配（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 时间复杂度：O(n)
空间复杂度：O(1)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
