【华为OD机试真题】真正的密码
题目描述
在一行中输入一个字符串数组，如果其中一个字符串的所有以索引0开头的子串在数组中都有，那么这个字符串就是潜在密码，
在所有潜在密码中最长的是真正的密码，如果有多个长度相同的真正的密码，那么取字典序最大的为唯一的真正的密码，求唯一的真正的密码。
测试样例1
输入
h he hel hell hello o ok n ni nin ninj ninja
输出
ninja
说明
按要求，hello、ok、ninja都是潜在密码。
检查长度，hello、ninja是真正的密码。
检查字典序，ninja是唯一真正密码。
测试样例2
输入
a b c d f
输出
f
说明
按要求，a b c d f 都是潜在密码。
检查长度，a b c d f 是真正的密码。
检查字典序，f是唯一真正密码。
解题思路
为了解决这个问题，我们可以分以下几个步骤进行：
- 输入处理：将输入的字符串分割成一个列表。
- 潜在密码识别：遍历每个字符串，检查它的所有前缀是否都在列表中。如果是，则该字符串是一个潜在密码。
- 真正密码筛选：在所有潜在密码中，找出最长的密码。如果有多个长度相同的密码，选择字典序最大的那个。
- 输出结果：输出找到的真正密码。
Python代码解析
def find_unique_passwords(strings):
# 创建一个集合以便快速查找
string_set = set(strings)
potential_passwords = []
for s in strings:
# 检查s的所有前缀
is_potential = True
for i in range(1, len(s) + 1):
if s[:i] not in string_set:
is_potential = False
break
if is_potential:
potential_passwords.append(s)
# 找到真正的密码
unique_password = ""
for pwd in potential_passwords:
# 选择长度最长的，若相同则字典序较大的
if (len(pwd) > len(unique_password)) or (len(pwd) == len(unique_password) and pwd > unique_password):
unique_password = pwd
return unique_password
if __name__ == "__main__":
input_string = input().strip()
strings = input_string.split()
result = find_unique_passwords(strings)
print(result)
