华为OD机试 - 最长的密码（Python/JS/C/C++ 2024 E卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

小王正在进行游戏大闯关，有一个关卡需要输入一个密码才能通过，密码获得的条件如下：

在一个密码本中，每一页都有一个由26个小写字母组成的密码，每一页的密码不同，需要从这个密码本中寻找这样一个最长的密码，从它的末尾开始依次去掉一位得到的新密码也在密码本中存在。

请输出符合要求的密码，如果有多个符合要求的密码，返回长度最大的密码。

若没有符合要求的密码，则返回空字符串。

二、输入描述

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

三、输出描述

一个字符串

四、测试用例

测试用例1：

1、输入

h he hel hell hello

2、输出

hello

3、说明

测试用例2：

1、输入

b ereddred bw bww bwwl bwwlm bwwln

2、输出

bwwlm

3、说明

五、解题思路

读取输入的字符串并将其拆分成字符串数组，表示密码本中的每一页密码。
将密码本的每个密码存入一个HashSet，以便于快速查找密码。
将密码数组按照密码长度进行降序排序，以确保我们能优先找到最长的密码。
对于每个密码，依次去掉末尾的字符，检查每个子密码是否存在于集合中。如果所有的子密码都存在，则返回这个密码。
如果找到了符合条件的密码，则输出这个密码；如果没有找到，则返回空字符串。

六、Python算法源码

# 导入集合模块
from collections import defaultdictdef find_longest_password(passwords):# 创建一个集合用于存储密码本中的密码password_set = set(passwords)longest_password = ""  # 存储符合条件的最长密码# 遍历每个密码for password in passwords:current = password  # 从当前密码开始# 检查当前密码的每个子密码while current:  # 当当前密码不为空if current not in password_set:  # 如果子密码不在集合中break  # 跳出循环current = current[:-1]  # 去掉末尾一个字符# 如果当前密码有效且长度大于已记录的最长密码if len(current) == 0 and len(password) > len(longest_password):longest_password = password  # 更新最长密码return longest_password  # 返回找到的最长密码# 主程序入口
if __name__ == "__main__":# 读取输入字符串，并拆分为数组passwords = input().strip().split()# 调用方法获取符合条件的最长密码result = find_longest_password(passwords)# 输出结果print(result)

七、JavaScript算法源码

function findLongestPassword(passwords) {// 创建一个集合用于存储密码本中的密码const passwordSet = new Set(passwords);let longestPassword = "";  // 存储符合条件的最长密码// 遍历每个密码for (const password of passwords) {let current = password;  // 从当前密码开始// 检查当前密码的每个子密码while (current.length > 0) {  // 当当前密码不为空if (!passwordSet.has(current)) {  // 如果子密码不在集合中break;  // 跳出循环}current = current.slice(0, -1);  // 去掉末尾一个字符}// 如果当前密码有效且长度大于已记录的最长密码if (current.length === 0 && password.length > longestPassword.length) {longestPassword = password;  // 更新最长密码}}return longestPassword;  // 返回找到的最长密码
}// 主程序入口
const input = require('fs').readFileSync('/dev/stdin', 'utf-8').trim();
const passwords = input.split(" ");  // 拆分输入为密码数组// 调用方法获取符合条件的最长密码并输出结果
console.log(findLongestPassword(passwords));

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_LENGTH 100  // 定义最大长度// 函数声明
char* findLongestPassword(char* passwords[], int n);int main() {char* passwords[MAX_LENGTH];  // 用于存储密码char buffer[200];  // 用于读取输入int n = 0;  // 密码数量// 读取输入fgets(buffer, sizeof(buffer), stdin);// 按空格分割输入char* token = strtok(buffer, " ");while (token != NULL) {passwords[n++] = token;  // 存储每个密码token = strtok(NULL, " ");  // 获取下一个密码}// 调用函数获取符合条件的最长密码char* result = findLongestPassword(passwords, n);// 输出结果printf("%s\n", result);return 0;
}char* findLongestPassword(char* passwords[], int n) {// 创建一个集合用于存储密码本中的密码char* passwordSet[MAX_LENGTH];int passwordSetSize = 0;// 将密码加入集合for (int i = 0; i < n; i++) {passwordSet[passwordSetSize++] = passwords[i];}char* longestPassword = "";  // 存储符合条件的最长密码// 遍历每个密码for (int i = 0; i < n; i++) {char* current = passwords[i];  // 从当前密码开始char temp[MAX_LENGTH];  // 用于存储当前密码的副本strcpy(temp, current);  // 复制当前密码// 检查当前密码的每个子密码while (strlen(temp) > 0) {  // 当当前密码不为空int found = 0;  // 标记是否找到for (int j = 0; j < passwordSetSize; j++) {if (strcmp(temp, passwordSet[j]) == 0) {  // 如果子密码在集合中found = 1;  // 标记找到break;  // 跳出循环}}if (!found) {break;  // 如果未找到，跳出循环}temp[strlen(temp) - 1] = '\0';  // 去掉末尾一个字符}// 如果当前密码有效且长度大于已记录的最长密码if (strlen(temp) == 0 && strlen(current) > strlen(longestPassword)) {longestPassword = current;  // 更新最长密码}}return longestPassword;  // 返回找到的最长密码
}

九、C++算法源码

#include <iostream>
#include <unordered_set>
#include <vector>
#include <string>using namespace std;string findLongestPassword(const vector<string>& passwords) {// 创建一个集合用于存储密码本中的密码unordered_set<string> passwordSet(passwords.begin(), passwords.end());string longestPassword;  // 存储符合条件的最长密码// 遍历每个密码for (const auto& password : passwords) {string current = password;  // 从当前密码开始// 检查当前密码的每个子密码while (!current.empty()) {  // 当当前密码不为空if (passwordSet.find(current) == passwordSet.end()) {  // 如果子密码不在集合中break;  // 跳出循环}current.pop_back();  // 去掉末尾一个字符}// 如果当前密码有效且长度大于已记录的最长密码if (current.empty() && password.length() > longestPassword.length()) {longestPassword = password;  // 更新最长密码}}return longestPassword;  // 返回找到的最长密码
}// 主程序入口
int main() {string input;  // 用于读取输入getline(cin, input);  // 读取一行输入vector<string> passwords;  // 存储密码的数组string temp;  // 临时变量存储单个密码// 按空格分割输入并存入数组for (char c : input) {if (c == ' ') {passwords.push_back(temp);  // 添加密码temp.clear();  // 清空临时变量} else {temp += c;  // 添加字符到临时变量}}if (!temp.empty()) {passwords.push_back(temp);  // 添加最后一个密码}// 调用函数获取符合条件的最长密码并输出结果cout << findLongestPassword(passwords) << endl;return 0;
}