Google Kickstart 2020 Round A Bundling题Python运行时错误求助

核心问题1：递归深度超限 #

你代码中采用递归实现字典树的DFS遍历，Python默认的递归深度上限为1000左右。如果官方测试用例中存在长度接近或超过1000的字符串，递归深度会超出系统限制，直接抛出RuntimeError: maximum recursion depth exceeded，这就是你提交后返回运行时错误的核心原因，和Python3.7/3.8的版本兼容性无关。你本地构造的测试用例字符串长度普遍较短，所以不会触发该问题。

次要问题：测试用例编号不符合要求 #

你外层循环的计数变量从0开始，输出的Case #x编号从0开始计数，不符合Google Kickstart要求的从1开始的编号规则，虽然不会触发运行时错误，但会导致所有测试用例被判为答案错误。

修复方案 #

方案1：调整递归深度限制 #

在代码开头加入递归深度调整语句即可解决递归溢出问题，同时修正测试用例计数逻辑即可：

import sys
sys.setrecursionlimit(1 << 25)

ans = 0
class Node:
    def __init__(self):
        self.children = {}
        self.count = 0
    
    def insert(self, key):
        node = self
        for char in key:
            idx = char
            if idx not in node.children:
                node.children[idx] = Node()
            node = node.children[idx]
            
        node.count +=1

    def resetAns(self):
        global ans
        ans = 0

    def dfs(self, dep=0, k=0):
        global ans
        for c in self.children:
            self.children[c].dfs(dep+1, k)
            self.count+=self.children[c].count
        while self.count >= k:
            self.count -= k
            ans+=dep
        return ans

def bundling():
    N, K = map(int, input().split())
    _node = Node()
    _node.resetAns()
    for _ in range(0, N):
        _v = input()
        _node.insert(_v)
    return _node.dfs(0, K)            

for case_num in range(1, int(input())+1):
    print("Case #{}: {}".format(case_num, bundling()))

方案2：迭代实现DFS（可选） #

如果担心递归深度调整带来的潜在风险，可以把DFS逻辑改为迭代后序遍历实现，完全规避栈溢出问题。

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