企业官网建设流程全解析

针对力扣（LeetCode）第1003题“检查替换后的词是否有效”，以下提供C++语言的详细解析与代码实现。该问题要求判断一个字符串s是否可以通过反复插入子串"abc"到任意有效字符串中来生成。

问题解构与核心逻辑

题目定义了一个字符串变换规则：一个有效的字符串"abc"，可以向其中任意位置插入另一个有效的字符串"abc"，从而生成新的有效字符串。给定一个字符串s，需要判断它是否是一个有效字符串。

关键约束与理解：

1. 基础有效串："abc"本身是有效的。
2. 生成规则：若t是有效的，则"a" + t + "bc"、"ab" + t + "c"或"abc" + t等（即在任意位置插入"abc"）也是有效的。这等价于，任何有效字符串都可以通过反复删除其中的一个子串"abc"最终变为空字符串。
3. 判断依据：因此，判断s是否有效的充要条件是，能否通过不断删除s中的子串"abc"，最终得到一个空字符串。

例如：

• s = "aabcbc"：可以删除中间的"abc"得到"abc"，再删除"abc"得到""，有效。
• s = "abcabcababcc"：经过一系列删除"abc"的操作，最终可变为空，有效。
• s = "abccba"：无法通过删除"abc"变为空，无效。

C++解法：栈模拟法

最直观高效的解法是使用栈（stack）或向量（vector）来模拟删除"abc"的过程。每当遇到字符‘c’时，就检查栈顶的两个字符是否是‘b’和‘a’（即是否构成了"abc"），若是则弹出它们，相当于删除了一个"abc"。

算法步骤

1. 初始化栈：使用一个字符栈stk。
2. 遍历字符串：
   • 对于当前字符ch：
     • 如果ch == ‘c’且栈的大小至少为2且栈顶的两个字符依次是‘b’和‘a’，则说明我们遇到了一个完整的"abc"的结尾。此时，将栈顶的‘b’和‘a’弹出（即删除这个"abc"）。
     • 否则，将当前字符ch压入栈中。
3. 判断结果：遍历完整个字符串后，如果栈为空，说明所有的字符都通过组成"abc"被成功“抵消”了，字符串有效；否则无效。

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…”），所有字符都会保留在栈中。

与其他解法的对比

除了栈模拟法，另一种思路是直接循环替换，但效率较低。

对于本题，栈模拟法是最优解，其思想与检查括号有效性的问题（如20.有效的括号）类似，都是利用栈进行匹配和抵消。

关联题目与模式总结

此题的核心是利用栈处理具有特定顺序和结构的序列，是一种经典的栈应用场景。

掌握这种“栈用于处理最近相关性”的算法模式，是解决许多字符串和序列处理问题的关键。

参考来源

• 1003. Check If Word Is Valid After Substitutions**
• 递归-24.两两交换链表中的节点-力扣(LeetCode)
• 递归-二叉树中的深搜-257.二叉树的所有路径-力扣(LeetCode)
• PAT_Basic Level_Practice_1003 (20)
• 枚举算法（c++版本）
• LeetCode Hot 100(三) C++版