如何在Python中按字典序生成两个字符串的交错序列？

我可以生成两个字符串的交错序列，但输出无法保证字典序。以下是输入、预期输出、当前实现代码及输出：

输入 #

2
nkb gl
bn zh

预期输出 #

Case #1:
glnkb
gnkbl
gnklb
gnlkb
ngkbl
ngklb
nglkb
nkbgl
nkgbl
nkglb
Case #2:
bnzh
bzhn
bznh
zbhn
zbnh
zhbn

当前代码 #

def interleave(A,B,ans,m,n,idx):
    if m == 0 and n == 0:
        print("".join(ans))
        return 
    if len(A)<=len(B):
        if m!=0:
            ans[idx]=A[0]
            interleave(A[1:],B,ans,m-1,n,idx+1)
        if n!=0:
            ans[idx]=B[0]
            interleave(A,B[1:],ans,m,n-1,idx+1)
    else:
        if n!=0:
            ans[idx]=B[0]
            interleave(A,B[1:],ans,m,n-1,idx+1)
        if m!=0:
            ans[idx]=A[0]
            interleave(A[1:],B,ans,m-1,n,idx+1)
t=int(input())
count=0
for i in range(t):
    count+=1
    print("Case #%d:"%count)
    A,B=input().split()
    m,n=len(A),len(B)
    ans=['']*(m+n)
    idx=0
    interleave(A,B,ans,m,n,idx)

当前输出 #

Case #1:
glnkb
gnlkb
gnkbl
gnklb
nkbgl
nkgbl
nkglb
nglkb
ngkbl
ngklb
Case #2:
bnzh
bznh
bzhn
zhbn
zbnh
zbhn

问题根源 #

当前代码的递归顺序由两个字符串的长度决定，这和字典序的排序逻辑完全无关，导致输出顺序混乱。要生成字典序的交错序列，必须每次优先选择当前可选字符中字典序更小的那个进行递归；当两个字符相等时，需要同时处理两种选择，避免遗漏可能的序列。

修正后的代码 #

def interleave(A, B, current):
    # 递归终止：两个字符串都为空，输出当前拼接结果
    if not A and not B:
        print(current)
        return
    
    # 同时有可选字符时，按字典序优先选择
    if A and B:
        if A[0] < B[0]:
            # 先选A的首字符递归
            interleave(A[1:], B, current + A[0])
            # 再选B的首字符递归
            interleave(A, B[1:], current + B[0])
        elif A[0] > B[0]:
            # 先选B的首字符递归
            interleave(A, B[1:], current + B[0])
            # 再选A的首字符递归
            interleave(A[1:], B, current + A[0])
        else:
            # 字符相等时，两种选择都要执行，确保所有序列被生成
            interleave(A[1:], B, current + A[0])
            interleave(A, B[1:], current + B[0])
    elif A:
        # 只剩A时，直接拼接剩余字符
        interleave(A[1:], B, current + A[0])
    elif B:
        # 只剩B时，直接拼接剩余字符
        interleave(A, B[1:], current + B[0])

t = int(input())
for case_num in range(1, t + 1):
    print(f"Case #{case_num}:")
    A, B = input().split()
    interleave(A, B, "")

代码说明 #

1. 简化递归参数：直接传递当前拼接的字符串current，避免使用列表修改，代码更简洁易维护。
2. 核心逻辑：每次比较两个字符串的首字符，优先递归选择字典序更小的选项；当字符相等时，两种选择都执行，保证所有可能的交错序列都被生成且按字典序排列。
3. 边界处理：当其中一个字符串为空时，直接拼接剩余字符即可，无需额外判断。

运行修正后的代码，输出将完全匹配预期的字典序结果。

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