如何用递归实现Python中两个二维整数列表的相等性判断，禁止循环和切片？

实现思路 #

• 我们需要4个下标指针分别跟踪两个输入列表的遍历进度：i1指向第一个列表的当前子列表，j1指向第一个列表当前子列表的当前元素；i2和j2对应第二个列表的相同含义。
• 递归过程中优先处理子列表遍历完成的情况：如果当前子列表的元素指针已走到末尾，直接跳到下一个子列表，重置元素指针为0即可。
• 两边都拿到有效元素后先做值比对，不等直接返回False，相等则同时推进两个元素指针进入下一层递归。
• 终止条件：任意一个列表的所有子列表遍历完成后，检查另一个列表是否也同时完成全部遍历即可。

完整代码 #

from typing import List

def compare_nested_lists(list_a: List[List[int]], list_b: List[List[int]]) -> bool:
    def helper(i1: int, j1: int, i2: int, j2: int) -> bool:
        # 终止条件1：list_a全部遍历完成
        if i1 == len(list_a):
            if i2 == len(list_b):
                return True
            # 跳过list_b剩余的空子列表
            if j2 == len(list_b[i2]):
                return helper(i1, j1, i2 + 1, 0)
            return False
        # 终止条件2：list_b全部遍历完成
        if i2 == len(list_b):
            # 跳过list_a剩余的空子列表
            if j1 == len(list_a[i1]):
                return helper(i1 + 1, 0, i2, j2)
            return False
        # 处理list_a当前子列表遍历完成的情况
        if j1 == len(list_a[i1]):
            return helper(i1 + 1, 0, i2, j2)
        # 处理list_b当前子列表遍历完成的情况
        if j2 == len(list_b[i2]):
            return helper(i1, j1, i2 + 1, 0)
        # 元素值比对
        if list_a[i1][j1] != list_b[i2][j2]:
            return False
        # 元素相等则推进指针进入下一层递归
        return helper(i1, j1 + 1, i2, j2 + 1)
    return helper(0, 0, 0, 0)

测试验证 #

• 输入compare_nested_lists([[1], [2, 3, 4]], [[1, 2], [3, 4]])，返回结果为True，符合题目示例要求。
• 输入compare_nested_lists([[1, 2], [3]], [[1], [4, 3]])，返回结果为False，元素比对不匹配。
• 输入compare_nested_lists([], [[]])，返回结果为True，两边整体元素序列均为空。

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