pythonjavacjsc_0">【华为OD-E卷-寻找密码 100分（python、java、c++、js、c）】

题目

小王在进行游戏大闯关，有一个关卡需要输入一个密码才能通过，密码获得的条件如下：
在一个密码本中，每一页都有一个由 26 个小写字母组成的若干位密码，每一页的密码不同，需要从这个密码本中寻找这样一个最长的密码，从它的末尾开始依次去掉一位得到的新密码也在密码本中存在。
请输出符合要求的密码，如果有多个符合要求的密码，则返回字典序最大的密码。
若没有符合要求的密码，则返回空字符串。

输入描述

• 密码本由一个字符串数组组成，不同元素之间使用空格隔开，每一个元素代表密码本每一页的密码

输出描述

• 一个字符串

备注

• 1 ≤ 密码本的页数 ≤ 10^5 1 ≤ 每页密码的长度 ≤ 10^5

用例

用例一：

输入：

h he hel hell hello

输出：

hello

用例二：

输入：

b ereddred bw bww bwwl bwwlm bwwln

输出：

bwwln

python_51">python解法

• 解题思路：
• 问题分析：

给定一个字符串列表 ps，我们需要找到其中一个最长的密码（即子串在列表中的“最长公共前缀”）。这个密码必须满足：该密码的所有前缀（去掉最后一个字符的子串）也必须在列表中出现。
思路：

排序：首先，将字符串按其长度和字典序排序。长度优先排序是为了更容易找到最长的密码，而字典序排序保证了较短的密码会排在较长的密码之前。

检查每个密码的前缀：对列表中每个字符串，我们需要检查它的所有前缀是否也在列表中。如果一个密码的所有前缀都在列表中，那么它就是合法的密码。

逆向遍历：由于我们需要找出最长的密码，因此可以从最长的密码开始检查（即从 ps 列表的最后一个元素开始检查）。如果一个密码满足条件（所有前缀都在列表中），则直接返回该密码；否则，继续检查下一个密码。

步骤：

排序：首先对 ps 按长度和字典序排序。
检查前缀：从排序后的列表中，逆序检查每个密码及其前缀是否都存在于列表中。如果存在，返回该密码。
如果没有找到符合条件的密码，返回空字符串。
复杂度分析：

排序的时间复杂度是 O(n log n)，其中 n 是密码列表的长度。
对每个密码检查其前缀，最坏情况下，检查所有密码的前缀的复杂度是 O(n * m)，其中 m 是平均密码长度。由于排序后的列表是按长度和字典序排列，因此在大部分情况下，最长的密码会在较前面的位置，因此可以提前返回。

python">ps = input().split()  # 输入密码列表def pwd_finder(ps):# 按照密码的长度优先，字典序次之排序ps.sort(key=lambda x: (len(x), x))# 将密码列表转换为集合，便于快速查找前缀是否存在ps_set = set(ps)# 逆序遍历密码列表，寻找最长符合条件的密码for p in reversed(ps):# 检查该密码的所有前缀是否都在集合中if all(p[:-i] in ps_set for i in range(1, len(p))):return p  # 如果条件满足，返回该密码return ""  # 如果没有符合条件的密码，返回空字符串# 输出结果
print(pwd_finder(ps))

java_98">java解法

• 解题思路
• 问题分析：

给定一组密码，我们需要找出最长的有效密码。一个密码是有效的当且仅当它的所有前缀（从最短到最大）都出现在密码列表中。
例如，对于密码 “abc”，它的前缀包括 “a”、“ab”、“abc”。如果这些前缀都出现在密码列表中，那么 “abc” 就是一个有效密码。
思路：

排序：首先，密码列表需要按字典序排序。这是因为，字典序的排列能够帮助我们更高效地检查密码的前缀是否存在。我们可以从最长的密码开始检查。
前缀检查：对每个密码，检查它的所有前缀（从最短到最长）是否也存在于密码列表中。如果有任意一个前缀不存在，则该密码不是有效密码。
TreeSet：我们使用 TreeSet 来保存密码，因为它能够自动排序，并且提供高效的前缀查找（通过 contains 方法）。TreeSet 保证了元素的排序，使得我们可以从最大的密码开始检查。
步骤：

将密码列表转换为 TreeSet，这样可以去除重复的密码并自动按字典序排序。
遍历 TreeSet 中的密码，从最大密码开始检查其所有前缀。
对每个密码，检查它的所有前缀是否都存在于 TreeSet 中。如果找到一个有效的密码，则返回该密码。
复杂度分析：

排序：将密码列表转换为 TreeSet 的时间复杂度是 O(n log n)，其中 n 是密码的数量。
前缀检查：对于每个密码，需要检查它的所有前缀，最坏情况下每个密码需要检查 O(m) 次，其中 m 是密码的最大长度。由于我们遍历整个 TreeSet，所以总复杂度为 O(n * m)。

java">import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入密码列表并分割成数组String[] passwords = sc.nextLine().split(" ");// 调用函数找出最长的有效密码并输出System.out.println(findMaxValidPassword(passwords));}// 找出最长的有效密码public static String findMaxValidPassword(String[] passwords) {// 使用 TreeSet 来存储密码，自动排序TreeSet<String> sortedSet = new TreeSet<>(Arrays.asList(passwords));String maxPassword = "";// 从排序后的密码集合中倒序遍历（从最长的密码开始）for (String pwd : sortedSet.descendingSet()) {// 检查当前密码的所有前缀是否都存在于集合中if (allPrefixesExist(pwd, sortedSet)) {maxPassword = pwd;break;  // 找到第一个有效密码，直接返回}}return maxPassword;  // 返回最长的有效密码}// 检查密码的所有前缀是否都存在于集合中private static boolean allPrefixesExist(String pwd, Set<String> sortedSet) {// 检查密码的所有前缀for (int len = pwd.length() - 1; len > 0; len--) {// 如果某个前缀不在集合中，返回 falseif (!sortedSet.contains(pwd.substring(0, len))) {return false;}}return true;  // 所有前缀都存在，返回 true}
}

C++解法

• 解题思路

更新中

C解法

• 解题思路

更新中

JS解法

• 解题思路

• 问题分析：

给定一个密码列表，我们需要找出其中的最长有效密码。一个密码是有效的当且仅当它的所有前缀（从最短到最大）都出现在密码列表中。
比如，如果密码是 “abc”，它的前缀包括 “a”、“ab”、“abc”。如果这些前缀都出现在密码列表中，那么 “abc” 就是一个有效密码。
思路：

去重和排序：首先，我们将密码列表去重，并按长度从大到小排序（如果长度相同，则按字典序倒序）。这样可以确保我们从最长的密码开始检查，如果找到符合条件的密码，立即返回它。
前缀检查：对每个密码，检查它的所有前缀是否也存在于密码列表中。可以通过 substring 方法生成所有的前缀，并检查这些前缀是否在密码集合中存在。
最优解法：一旦找到一个密码的所有前缀都在集合中，我们立即返回该密码；否则继续检查下一个密码。
步骤：

将密码列表转换为 Set 以去除重复的密码并提高查找效率。
将密码列表按长度从大到小排序（相同长度时按字典序倒序排序），这样可以确保我们优先检查最长的密码。
对每个密码，检查它的所有前缀是否在 Set 中存在。如果满足条件，返回该密码。
如果没有任何密码符合条件，返回空字符串。
复杂度分析：

排序的时间复杂度是 O(n log n)，其中 n 是密码的数量。
对每个密码，最坏情况下需要检查它的所有前缀，检查每个前缀的时间复杂度为 O(m)，其中 m 是密码的最大长度。因此总时间复杂度是 O(n * m)，其中 n 是密码的数量，m 是密码的最大长度

javascript">const readline = require("readline");
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });// 监听输入行并处理
rl.on("line", (line) => {const passwords = line.split(" ");  // 将输入的密码字符串按空格分割为数组console.log(findPassword(passwords));  // 调用函数并输出结果
});// 寻找最长有效密码的函数
function findPassword(passwords) {const pwSet = new Set(passwords);  // 将密码列表转换为 Set，去重并提高查找效率// 按密码长度从大到小排序，长度相同则按字典序倒序排序passwords.sort((a, b) => b.length - a.length || b.localeCompare(a));// 遍历排序后的密码列表for (let pw of passwords) {let valid = true;  // 标记当前密码是否有效// 检查密码的所有前缀for (let i = pw.length - 1; i > 0; i--) {if (!pwSet.has(pw.substring(0, i))) {  // 如果某个前缀不在集合中，则当前密码无效valid = false;break;}}// 如果所有前缀都在集合中，则返回当前密码if (valid) return pw;}// 如果没有符合条件的密码，返回空字符串return "";
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏