python 通过返回bool的函数优化字符串猜测表的搜索算法

xytpbqjk  于 2022-12-10  发布在  Python
关注(0)|答案(1)|浏览(105)

我努力想找出完成这个任务的最有效的办法:
函数check()包含一个字符串列表。如果参数字符串是列表中任意字符串的一部分,则调用该函数时将返回True。否则将返回False
下面是我的代码:

import string
from tqdm import tqdm

def check(text):
    """Returns True if input text is part of any of the strings in the list"""
    strings = ["we ", "_want", "t0", "gu@ess", "these-", "str1ngs"]
    return any(text in substring for substring in strings)

def remove_partials(input_list):
    """Removes strings from the input list they are a substring of any other string in the list"""
    substrings = []
    for item in input_list:
        for item_2 in input_list:
            if item != item_2 and item_2 in item:
                substrings.append(item_2)

    for partial in substrings:
        try:
            input_list.remove(partial)
        except ValueError:
            pass

    return input_list

charset = f"{string.ascii_lowercase}{string.digits}@-_. "
known = charset
tried = []
result = []

while len(known) > 0:
    found = []

    for prefix in (pbar_2 := (tqdm(known, leave=False))):
        pbar_2.set_description(prefix)

        for char in (pbar := (tqdm(charset, leave=False))):

            substring = f"{prefix}{char}"
            pbar.set_description(char)

            if substring not in tried:

                if check(substring) and substring not in found:
                    tqdm.write(f"{substring}")
                    found.append(substring)
                    result.append(substring)

            tried.append(substring)

    known = found

print()
print(remove_partials(result))

我想用尽可能少的检查来猜测列表的内容,使用check()函数,只知道字符集(alphanumeric + -_@.[space])并显示进度(我使用的是tqdm)。
我的代码确实完成了这一点,但效率非常低。例如,如果“字符串”在列表中,它会同时对“字符串”、“字符串”和“字符串”执行检查,我觉得这可以优化。

1hdlvixo

1hdlvixo1#

以下是一些提示,可以帮助您解决问题:
1.字符串列表不会更改,因此您可以全局定义它
1.将长度为n的字符串与长度为nm字符串进行比较,每个字符串的复杂度为O(n*m)
1.您可以对字符串进行预处理并创建一个trie,这将把搜索复杂度降低到O(n),因为您只需要检查匹配项。

相关问题