string - 递归和内存算法的运行时错误

Question

我正在尝试解决 https://www.hackerrank.com/challenges/password-cracker/problem问题这是问题陈述

有 N 个用户在 CuteKittens.com 网站上注册。他们每个人都有一个唯一的密码，由 pass[1]、pass[2]、...、pass[N] 表示。由于这是一个非常可爱的网站，很多人都想访问那些非常可爱的小猫照片。但是顽固的管理员不希望这个网站对公众开放。因此只有那些拥有密码的人才能访问它。

Yu 是一位了不起的黑客，他在他们的密码验证系统中发现了一个漏洞。密码验证系统也接受以任何顺序串联一个或多个密码的字符串。任何密码都可以在该字符串中出现 0 次或多次。他有权访问这N个密码中的每一个，并且还有一个字符串loginAttempt，他必须判断这个字符串是否被网站的密码验证系统所接受。

例如，如果有 3 个用户使用密码 {"abra", "ka", "dabra"}，则一些有效组合是 "abra"(pass[1])、"kaabra"(pass[ 2]+pass[1]), "kadabraka"(pass[2]+pass[3]+pass[2]), "kadabraabra"(pass[2]+pass[3]+pass[1]) 等等上。

输入格式

第一行包含一个整数T，测试用例的总数。然后是 T 个测试用例。每个测试用例的第一行包含 N，即具有密码的用户数。第二行N个空格分隔的字符串，pass[1] pass[2] ... pass[N]，代表每个用户的密码。第三行包含一个字符串，loginAttempt，Yu 必须告诉它是否会被接受

我尝试使用递归和记忆化来解决它这是我在 python3 中的解决方案

#!/bin/python3

import sys

def passwordCracker(passwords, attempt, memo):

    if attempt in memo:
        return memo[attempt]

    for pwd in passwords:
        if attempt.startswith(pwd):
            if len(pwd) == len(attempt):
                memo[attempt] = [pwd]

                return [pwd]

            prefix_size = len(pwd)
            cracked_pwds = passwordCracker(passwords, attempt[prefix_size:], memo)

            if len(cracked_pwds) != 0:              
                cracked_pwds.append(pwd)               
                memo[attempt] = list(cracked_pwds)

                return cracked_pwds

    memo[attempt] = []

    return []

def print_passwords(passwords, attempt, memo):

    #passwords.sort(key = len)
    result = passwordCracker(passwords, attempt, memo)
    result.reverse()
    #print (memo)
    if len(result) == 0:
        print ("WRONG PASSWORD")
    else:
        res_str = result[0] 
        for w in result[1:]:
            res_str = res_str + " " + w
        print(res_str)

if __name__ == "__main__":
    t = int(input().strip())
    for a0 in range(t):
        memo = {}
        n = int(input().strip())
        passwords = input().strip().split(' ')
        attempt = input().strip()
        print_passwords(passwords, attempt, memo)

但是很多测试用例都因运行时错误或超出时间限制而失败。它失败的一个特定测试用例是输入

1
10
a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

我不知道如何改进它。谁能提出更好的替代解决方案。

Answer 1

您的 memo[] 缓存效率极低。

在本练习中，您所要做的就是在 attempt 中插入空格，以便将其分隔为有效密码，或者如果不可能则返回 WRONG PASSWORD。

因此，您唯一需要跟踪的信息就是应该在何处添加这些空格。

您可以在没有字典的情况下执行此操作，也无需创建任何匹配字符串的部分列表。

只需从一个简单的数字列表开始(例如，memo = [-1] * len(attempt))。每当找到匹配项时，存储下一个不匹配字符的索引。如果这个索引恰好等于len(attempt)，那么你显然可以停止搜索。如果特定位置不存在匹配项，则也存储该结果。

匹配成功后，遍历字符串偏移量列表以找出需要插入空格的位置。

---

编辑:

我在 HackerRank 上解决了这个问题。上面的方法基本上工作正常，但需要一些小的调整才能通过所有测试。特别是，您可能需要调用 sys.setrecursionlimit 以允许更高级别的递归。