如何用递归与记忆化判断字符串是否为另外两字符串的混合串？

混合串定义 #

若字符串z是字符串a和b的混合串，需同时满足：

• z的长度等于a与b的长度之和
• a、b无重复字符
• z中a、b的字符各自保持原有顺序

有效示例 #

a = "wxy"
b = "mnop"
z = "wmxnoyp"

z是合法混合串：a的字符w→x→y在z中顺序未变，b的字符m→n→o→p的顺序也完全保留。

无效示例 #

a = "tuim"
b = "oprn"
z = "moiprunt" 

z不是混合串：a的字符顺序被打乱（比如a的首字符t出现在z末尾，而a的第4位字符m却排在z开头），不符合"各自保持原顺序"的要求。

记忆化二维数组详解 #

我们用memo[i][j]存储已计算的子问题结果，其中：

• i：已匹配a的前i个字符
• j：已匹配b的前j个字符
• memo[i][j]：表示用a的前i个字符 + b的前j个字符，能否组成z的前i+j个字符，值为True/False

结合示例的表格结构 #

以有效示例a="wxy"（长度3）、b="mnop"（长度4）、z="wmxnoyp"（长度7）为例，memo是4×5的数组（i取值0_{3，`j`取值0}4）：

填充规则

1. 边界初始化：
   • memo[0][0] = True：空串+空串匹配空的z前缀
   • 第一行memo[0][j]：仅用b的前j个字符匹配z的前j个字符，需满足b[j-1] == z[j-1]且memo[0][j-1]为True
   • 第一列memo[i][0]：仅用a的前i个字符匹配z的前i个字符，需满足a[i-1] == z[i-1]且memo[i-1][0]为True
2. 内部填充：
   对于memo[i][j]，只要满足以下任一条件则为True：
   • a[i-1] == z[i+j-1] 且 memo[i-1][j] == True：取a的第i个字符匹配z的当前位置，且之前的子问题成立
   • b[j-1] == z[i+j-1] 且 memo[i][j-1] == True：取b的第j个字符匹配z的当前位置，且之前的子问题成立

递归+记忆化代码实现 #

def is_interleave(a: str, b: str, z: str) -> bool:
    len_a, len_b, len_z = len(a), len(b), len(z)
    # 长度不匹配直接排除
    if len_a + len_b != len_z:
        return False
    
    # 记忆化数组：-1=未计算，1=True，0=False
    memo = [[-1] * (len_b + 1) for _ in range(len_a + 1)]
    
    def dfs(i, j):
        # 已计算过直接返回结果
        if memo[i][j] != -1:
            return memo[i][j] == 1
        # 所有字符匹配完成，返回成功
        if i == len_a and j == len_b:
            memo[i][j] = 1
            return True
        
        match = False
        # 尝试匹配a的下一个字符
        if i < len_a and a[i] == z[i + j]:
            match = match or dfs(i + 1, j)
        # 尝试匹配b的下一个字符
        if j < len_b and b[j] == z[i + j]:
            match = match or dfs(i, j + 1)
        
        memo[i][j] = 1 if match else 0
        return match
    
    return dfs(0, 0)

代码说明 #

• 先做长度校验，不满足直接返回False，避免无效递归
• 用memo数组缓存已计算的子问题结果，避免重复计算导致的性能损耗
• 递归函数dfs(i,j)从a的第i位、b的第j位开始，判断能否匹配z的后续字符
• 每次递归尝试两种路径：取a的当前字符，或取b的当前字符，只要有一条路径可行就返回True

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