我努力想找出完成这个任务的最有效的办法:
函数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)。
我的代码确实完成了这一点,但效率非常低。例如,如果“字符串”在列表中,它会同时对“字符串”、“字符串”和“字符串”执行检查,我觉得这可以优化。
1条答案
按热度按时间1hdlvixo1#
以下是一些提示,可以帮助您解决问题:
1.字符串列表不会更改,因此您可以全局定义它
1.将长度为
n
的字符串与长度为n
的m
字符串进行比较,每个字符串的复杂度为O(n*m)
1.您可以对字符串进行预处理并创建一个trie,这将把搜索复杂度降低到
O(n)
,因为您只需要检查匹配项。