针对力扣（LeetCode）第1003题“检查替换后的词是否有效”，以下提供C++语言的详细解析与代码实现。该问题要求判断一个字符串 s 是否可以通过反复插入子串 "abc" 到任意有效字符串中来生成。
问题解构与核心逻辑
题目定义了一个字符串变换规则：一个有效的字符串 "abc"，可以向其中任意位置插入另一个有效的字符串 "abc"，从而生成新的有效字符串。给定一个字符串 s，需要判断它是否是一个有效字符串。
关键约束与理解：
例如：
- s = "aabcbc"：可以删除中间的 "abc" 得到 "abc"，再删除 "abc" 得到 ""，有效。
- s = "abcabcababcc"：经过一系列删除 "abc" 的操作，最终可变为空，有效。
- s = "abccba"：无法通过删除 "abc" 变为空，无效。
C++解法：栈模拟法
最直观高效的解法是使用栈（stack）或向量（vector）来模拟删除 "abc" 的过程。每当遇到字符 ‘c’ 时，就检查栈顶的两个字符是否是 ‘b’ 和 ‘a’（即是否构成了 "abc"），若是则弹出它们，相当于删除了一个 "abc"。
算法步骤
- 对于当前字符 ch：
- 如果 ch == ‘c’ 且 栈的大小至少为2 且 栈顶的两个字符依次是 ‘b’ 和 ‘a’，则说明我们遇到了一个完整的 "abc" 的结尾。此时，将栈顶的 ‘b’ 和 ‘a’ 弹出（即删除这个 "abc"）。
- 否则，将当前字符 ch 压入栈中。
C++代码实现
#include <string>
#include <stack>
using namespace std;
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (char ch : s) {
// 当前字符是 'c'，检查栈顶是否能构成 "abc"
if (ch == 'c') {
// 栈中至少要有两个元素，且它们依次是 'b' 和 'a'
if (stk.size() >= 2 && stk.top() == 'b') {
stk.pop(); // 弹出 'b'
if (stk.top() == 'a') {
stk.pop(); // 弹出 'a'
continue; // 成功匹配一个"abc"，跳过当前'c'的入栈
} else {
// 第二个字符不是 'a'，恢复弹出的 'b' 并压入 'c'
stk.push('b');
stk.push(ch);
}
} else {
// 栈中元素不足或栈顶不是 'b'，直接压入 'c'
stk.push(ch);
}
} else {
// 当前字符是 'a' 或 'b'，直接压入栈
stk.push(ch);
}
}
// 最终栈为空则字符串有效
return stk.empty();
}
};
代码关键点解析：
- 栈的使用：栈完美地模拟了字符串的拼接和删除过程。压栈相当于添加字符，当遇到 ‘c’ 并满足条件时，连续弹出 ‘b’ 和 ‘a’ 相当于删除了一个完整的 "abc"。
- 条件判断顺序：检查 ‘c’ 时，必须先判断栈大小再访问栈顶，避免运行时错误。
- 恢复操作：在 if (stk.top() == ‘b’) 分支内，如果弹出 ‘b’ 后发现栈顶不是 ‘a’，需要将弹出的 ‘b’ 和当前的 ‘c’ 都压回去，保持状态正确。这是处理类似 "abac" 这种场景所必需的。
优化后的简洁代码
上述逻辑可以写得更紧凑。我们可以利用一个事实：当遇到 ‘c’ 时，我们只关心栈顶是否恰好是 ‘b’ 和 ‘a’。更简洁的写法如下：
class Solution {
public:
bool isValid(string s) {
vector<char> stk; // 使用vector模拟栈，便于访问倒数第二个元素
for (char ch : s) {
stk.push_back(ch);
int n = stk.size();
// 每当栈顶三个字符构成 "abc"，就将它们移除
if (n >= 3 && stk[n-1] == 'c' && stk[n-2] == 'b' && stk[n-3] == 'a') {
stk.pop_back();
stk.pop_back();
stk.pop_back();
}
}
return stk.empty();
}
};
优化点解析：
- 使用 vector<char>：可以直接通过索引访问倒数第二、第三个元素，比 stack 更便捷。
- 统一处理：无论什么字符都先压入，然后立即检查栈顶是否形成了 "abc"。逻辑更清晰，无需复杂的条件分支。
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符最多入栈和出栈一次。
- 空间复杂度：O(n)。在最坏情况下（如 s = “aaaa…”），所有字符都会保留在栈中。
与其他解法的对比
除了栈模拟法，另一种思路是直接循环替换，但效率较低。
| 核心思想 | 模拟插入/删除过程，遇到 “abc” 即抵消 | 在字符串中循环查找并删除子串 “abc” |
| 实现 | 单次遍历，使用栈或向量 | 使用 while 循环和 string::find、string::erase |
| 时间复杂度 | O(n)，每个字符处理一次 | O(n²)，每次查找和删除都可能涉及字符串移动 |
| 空间复杂度 | O(n) | O(1) 或 O(n)，取决于实现 |
| 性能 | 高效，适合长字符串 | 在字符串较长时性能差 |
| 代码简洁性 | 较简洁 | 直观但效率低 |
对于本题，栈模拟法是最优解，其思想与检查括号有效性的问题（如20.有效的括号）类似，都是利用栈进行匹配和抵消。
关联题目与模式总结
此题的核心是利用栈处理具有特定顺序和结构的序列，是一种经典的栈应用场景。
| 1003. 检查替换后的词是否有效 | 检查并消除连续的 “abc” | 本题本身 |
| 20. 有效的括号 | 检查并匹配成对的括号 (), {}, [] | 模式完全相同，都是遇到右元素（如 ), c）时检查栈顶是否是对应的左元素 |
| 1047. 删除字符串中的所有相邻重复项 | 删除相邻且相同的字符 | 简化版，只需比较栈顶与当前字符是否相同 |
| 剑指 Offer 31. 栈的压入、弹出序列 | 判断一个序列是否为另一个栈的弹出顺序 | 同样是栈的模拟和匹配逻辑 |
掌握这种“栈用于处理最近相关性”的算法模式，是解决许多字符串和序列处理问题的关键。
参考来源
- 1003. Check If Word Is Valid After Substitutions**
- 递归-24.两两交换链表中的节点-力扣(LeetCode)
- 递归-二叉树中的深搜-257.二叉树的所有路径-力扣(LeetCode)
- PAT_Basic Level_Practice_1003 (20)
- 枚举算法（c++版本）
- LeetCode Hot 100(三) C++版
