双操作规则下构造字典序最小字符串的求解与代码调试

给定三个字符串a、b、c，初始状态下b、c均为空串，仅允许通过以下两种操作构造字符串c：

• move1：取出字符串a的首字符，追加到字符串b的末尾
• move2：取出字符串b的尾字符，追加到字符串c的末尾
  遵循上述规则可以生成多个不同的c串，要求返回其中字典序最小的结果。

示例：输入a = 'dad'，合法构造得到的最小字典序结果为add，构造流程如下：

1. 取a[0]追加到b，状态：a = "ad", b = 'd', c=''
2. 取a[0]追加到b，状态：a = 'd', b = 'da', c = ''
3. 取b[-1]追加到c，状态：a = 'd', b='d', c = 'a'
4. 取a[0]追加到b，状态：a='', b='dd', c ='a'
5. 取b[-1]追加到c，状态：a='', b='d', c='ad'
6. 取b[-1]追加到c，状态：a='', b='', c='add'

你写的递归枚举代码存在两类问题，导致无法通过全部测试用例：

1. 基础笔误导致运行错误
   代码中存在两处未定义变量的错误：
   • 执行move1操作时，拼接st2写的是st2+st[0]，不存在st变量，正确应为取st1的首字符，即st2 + st1[0]
   • 判断是否可以执行move2的条件写的是if st:，同样不存在st变量，正确应为判断栈st2是否非空，即if st2:
2. 暴力枚举复杂度太高，大数据量超时/爆内存
   就算修正笔误，递归枚举所有合法序列的时间复杂度是卡特兰数级别，约为O(4ⁿ/√n)，当输入字符串长度超过15时，枚举量就会达到百万级，长度到20以上直接会超时或者内存溢出，只能通过小规模测试用例。

你贴出的原始错误代码如下：

class Solution:
    def solve(self, input1: int, input2: str) -> str:
        res = []
        def rec(st1,st2, st3):
            if not st1 and not st2:
                res.append(st3[:])
                return
            
            if st1:
                rec(st1[1:], st2+st[0], st3) # 笔误：st不存在，应为st1[0]
            if st: # 笔误：st不存在，应为st2
                rec(st1, st2[:len(st2)-1], st3+st2[-1])
        rec(input2, "", "")
        res.sort()
        return res[0]

这道题本质是求顺序入栈序列的最小字典序出栈序列，b就是中间栈，不需要枚举所有可能，用贪心策略每一步选最优选择即可，基础实现时间复杂度O(n²)，可以轻松应对长度1e3以内的输入，预处理后缀最小值后可以优化到O(n)。

贪心规则 #

每一步做决策时遵循以下逻辑：

• 如果栈为空，只能执行入栈操作（move1）
• 如果所有待入栈的字符都已经入栈（a为空），直接把栈中剩余字符依次弹出追加到结果即可
• 其余情况，比较当前栈顶字符 和 所有还没入栈的剩余字符中的最小值：
  • 如果剩余字符里存在比栈顶更小的字符：不能弹出栈顶，否则大字符排在前面会让字典序变大，继续入栈
  • 如果栈顶字符已经小于等于剩余所有未入栈的字符：直接弹出栈顶到结果，这是当前能选的最小字符

代码实现 #

class Solution:
    def solve(self, input1: int, a: str) -> str:
        stack = []
        res = []
        n = len(a)
        ptr = 0 # 指向a中下一个要入栈的位置
        while ptr < n or stack:
            # 栈不为空，且（所有字符已入栈 或 栈顶小于等于后续未入栈的最小字符），就弹出
            if stack and (ptr == n or stack[-1] <= min(a[ptr:])):
                res.append(stack.pop())
            else:
                # 否则执行入栈操作
                stack.append(a[ptr])
                ptr += 1
        return ''.join(res)

上述代码可以直接通过示例用例，输入a='dad'时返回结果'add'，符合预期。

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