LeetCode交错字符串问题：双栈解法为何失效？为何不适用栈

核心思路缺陷 #

你的解法本质是无回溯的贪心策略，致命问题在于没有处理分支选择场景：当s1、s2的栈顶字符同时和s3当前字符相等时，你默认优先弹出s1的栈顶完成匹配，一旦这个选择是错误的，没有任何回退机制，必然会出现误判。

可复现的失效用例 #

拿下面这组参数跑你的代码，就会出现明确的误判：

• s1 = "XY"
• s2 = "XZ"
• s3 = "XZXY"
  首先确认合法性：这个s3是完全符合要求的交错字符串，s3前两位X、Z来自s2，后两位X、Y来自s1，两个字符串的字符顺序都没有被打乱，正确结果应该返回true。
  我们顺着你的代码逻辑走一遍执行流程，就能看到问题：

1. 初始化栈时，s1逆序压入a栈后栈顶是X，s2逆序压入b栈后栈顶也是X
2. 遍历到s3第一位X时，代码优先匹配a栈，弹出a栈的X，此时a栈只剩Y
3. 遍历到s3第二位Z时，a栈顶是Y不匹配，b栈顶是X也不匹配，触发无匹配则i++的逻辑，直接跳过这个Z
4. 遍历到s3第三位X时，匹配b栈弹出X，b栈只剩Z；遍历到s3第四位Y时，匹配a栈弹出Y，a栈为空
5. 遍历结束后b栈还残留Z没有弹出，代码直接返回false，和正确结果相悖
   问题根源非常明确：第一个出现的X本应该匹配给s2，才能让后续的Z正常弹出，但你的贪心逻辑优先把它配给了s1，直接把路走死了。

额外的思路偏差 #

你提到的「长度满足len(s3)=len(s1)+len(s2)前提下，只要s1、s2都是s3的子序列，s3就是合法交错串」这个性质本身是成立的，但你的栈实现并没有正确完成子序列校验：贪心弹连续栈顶的逻辑，只会机械匹配最先遇到的连续相同字符，不会全局选择正确的匹配位置，自然没法保证找到合法的子序列拆分方式。

修正方向 #

栈结构本身可以解这个题，但不能用你现在这种一冲到底的贪心逻辑：

• 当遇到两个栈顶都能匹配当前字符的分支点时，需要记录当前的遍历指针位置、两个栈的状态，先尝试一个方向匹配，如果后续走不通（出现字符无法匹配、最后栈不为空的情况），就回退到分支点尝试另一个方向，本质就是带状态记录的深度优先搜索。
• 另外你的代码还有个语法小错误：第二个内层while里的flag=1语句末尾漏了分号，直接编译不过。

内容的提问来源于stack exchange，提问作者ksquare