我们来看一下这道题目到底哪里不错。
题目描述
小王在进行游戏大闯关，有一个关卡需要输入一个密码才能通过，密码获得的条件如下：在一个密码本中，每一页都有一个由
26
个小写字母组成的若干位密码，从它的末尾开始依次去掉一位得到的新密码也在密码本中存在。请输出符合要求的密码，如果由多个符合要求的密码，则返回字典序最大的密码。若没有符合要求的密码，则返回空字符串。
输入
密码本由一个字符串数组组成，不同元素之间使用空格隔开，每一个元素代表密码本每一页的密码。
输出
一个字符串
示例一
输入
h he hel hell hello
输出
hello
说明
"hello"
从末尾依次去掉一位得到的
"hell"
,
"hel"
,
"he"
,
"h"
在密码本中都存在。
示例二
输入
b eredderd bw bww bwwl bwwlm bwwln
输出
bwwln
解题思路
最朴素的解法是将所有字符串都存在一个哈希表
password_set
中，然后遍历字符串数组中的每一个密码
password
，对每一个
password
都去判断其所有的前缀是否也位于
password_set
中。如果满足，则把
password
和
ans
比较并且更新
ans
。
这种做法虽然思路直接简单，但略显笨重，会出现很多重复计算。
以示例一为例子：
-
对于单词
hell
，需要分别考虑前缀
h
、
he
、
hel
-
对于单词
hello
，需要分别考虑前缀
h
、
he
、
hel
、
hell
-
前缀
h
、
he
、
hel
对于单词
hello
而言，显然是重复计算了。 -
假设我们已经知道单词
hell
是一个有效的密码，那么对于单词
hello
，我们就只需要去考虑
hell
这个前缀，而不需要再去考虑
h
、
he
、
hel
这三个前缀了。 -
换句话说，单词
hello
是否是一个有效的密码，可以由其去掉末尾的前缀
hell
是否是一个有效的密码来决定。这本质上是一种动态规划的思想。（动态规划更详细的内容在后面会讲到）
如果用动态规划的语言来描述，即：
password
是一个有效密码，****当且仅当
password[:-1]
是一个有效密码。
那么现在问题就变成了：如何能够在判断
password
是一个有效密码之前，就先判断得到
password[:-1]
**
是否有效？
**这个问题就很简单了。我们只需要对原来的字符串数组
password_lst
按照字典序进行排序，就可以保证在
password
进行判断时，
password[:-1]
已经被判断过了。
我们可以构建一个用于储存所有有效密码的哈希集合
valid_set
。然后遍历排序过的字符串数组
password_lst
中的每一个密码
password
，如果其去掉末尾的前缀
password[:-1]
位于
valid_set
中，说明
password
也是一个有效密码，需要将其加入
valid_set
中，同时更新
ans
。
for password in password_lst:
if password[:-1] in valid_set:
valid_set.add(password)
ans = password
注意
valid_set
初始化时要包含一个空串
""
，因为只有一个字符的密码比如
"h"
，去掉最末尾的字符之后是一个空串
""
，
"h"
理应是一个有效的密码，故
""
应该存在于
valid_set
中。即：
valid_set = {""}
代码
解法一
（哈希集合暴力解法，只能通过部分用例）
# 题目：2023Q1A-寻找密码
# 作者：许老师
# 代码看不懂的地方，请直接在群上提问，不要过夜！
# 将输入字符串分割为字符串数组，并且存入哈希集合中
password_set = set(input().split())
# 初始化答案为一个空字符串
ans = str()
# 遍历哈希集合password_set中的所有密码单词password
for password in password_set:
# password有可能不符合要求，设置一个标记isValid，初始化为True表示该密码符合要求
isValid = True
# 遍历password的所有前缀password[:i]，判断前缀是否均位于password_set中
for i in range(1, len(password)-1):
# 若某一个前缀不位于哈希集合中，则该password无效，修改isValid为False，且退出循环
if password[:i] not in password_set:
isValid = False
break
# isValid为True，说明该password有效，将其与ans比较并更新ans
if isValid:
ans = max(ans, password)
print(ans)
时空复杂度
时间复杂度：
O(NM)
。遍历每个单词、每个字符所需的时间。
空间复杂度：
O(NM)
。
N
为单词数目，
M
为单词平均长度。
解法二
（哈希集合优化解法，含DP思想，可以通过全部用例）
# 题目：2023Q1A-寻找密码
# 作者：许老师
# 代码看不懂的地方，请直接在群上提问，不要过夜！
password_lst = input().split()
# 对输入的字符串数组进行升序排序
password_lst.sort()
# 初始化一个表示有效密码的哈希集合，初始化其中仅包含空字符串
valid_set = {""}
# 初始化答案为空字符串
ans = ""
# 从头到尾遍历升序字符串数组password_lst中的密码password
for password in password_lst:
# 如果password去掉最后一位的结果password[:-1]，位于valid_set哈希集合中
# 说明当前的password是一个有效密码，将其加入valid_set，同时更新ans
if password[:-1] in valid_set:
valid_set.add(password)
ans = password
print(ans)
时空复杂度
时间复杂度：
O(NlogN)
。排序所需的时间复杂度。
空间复杂度：
O(NM)
。哈希集合所占的额外空间。
N
为单词数目，
M
为单词平均长度。
解法三*
（前缀树解法，不要求掌握，感兴趣的同学可以研究一下）
# 题目：2023Q1A-寻找密码
# 作者：许老师
# 代码看不懂的地方，请直接在群上提问，不要过夜！
# 前缀树的节点类
class Trie():
def __init__(self) -> None:
self.children = [None] * 26
self.isEnd = False
# 将单词word加入前缀树的函数
def addword(self, word):
node = self
for ch in word:
ch_idx = ord(ch) - 97 # ASCII to idx
# 以下两行用来通过最后一个用例..输入了非小写字母的字符串
if ch_idx > 25 or ch_idx < 0:
return
if node.children[ch_idx] is None:
node.children[ch_idx] = Trie()
node = node.children[ch_idx]
node.isEnd = True
# 检查word的所有前缀是否存在的函数
def checkPrefix(self, word):
node = self
for ch in word:
ch_idx = ord(ch) - 97
if node.children[ch_idx].isEnd == False:
return False
node = node.children[ch_idx]
return True
if __name__ == "__main__":
lst = input().split()
ans = ""
root = Trie()
for word in lst: # 构建前缀树
root.addword(word)
for word in lst:
if len(word) < len(ans):
continue
if root.checkPrefix(word):
if len(word) > len(ans):
ans = word
elif len(word) == len(ans):
ans = max(ans, word)
print(ans)
时空复杂度
时间复杂度：
O(NM)
。建树、检查前缀的时间。
空间复杂度：
O(D)
。
N
为单词数目，
M
为单词平均长度，
D
为前缀树的节点数，远小于
NM
。