2023年华为OD机考真题：寻找密码

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：寻找密码
知识点树
时间限制：1s 空间限制：32MB 限定语言：不限
题目描述：
小王在进行游戏大闯关，有一个关卡需要输入一个密码才能通过。密码获得的条件如下：在一个密码本中，每一页都有一个由26个小写字母组成的若干位密码，每一页的密码不同，需要从这个密码本中寻找这样一个最长的密码，从它的末尾开始依次去掉一位得到的新密码也在密码本中存在。请输出符合该要求的密码，如果有多个符合要求的密码，则返回字典序最大的密码。若没有符合要求的密码，则返回空字符串。
输入描述：
密码本由一个字符串数组组成，不同元素之间使用空格隔开，每一个元素代表密码本每一页的密码
输出描述：
一个字符串
补充说明：
1 <= 密码本的页数 <= 105
1 <= 每页密码的长度 <= 105
示例1
输入：
h he hel hell hello
输出：
hello
说明：
“hello”从末尾依次去掉一位得到的 “hell”，”hel”，”he”和”h”在密码本中都存在。
示例2
输入：
b eredderd bw bww bwwl bwwlm bwwln
输出：
bwwln
说明：
“bwwlm ” 和 “bwwln” 从末尾开始依次去掉一位得到密码在密码本中都存在。但是 “bwwln” 比 “bwwlm” 字典序排序大，所以应该返回”bwwln”
解题思路：
将输入的密码本放在list中，主要是想用list的contains函数
循环求出所有符合密码规则的字符串，取较长的字符串作为密码；如果字符串长度相等，则取字典序大的作为密码

代码实现：

package com.codernav.demo.hwod.exam;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @title 寻找密码
 * @Description 小王在进行游戏大闯关，有一个关卡需要输入一个密码才能通过。
 * 密码获得的条件如下：在一个密码本中，每一页都有一个由26个小写字母组成的若干位密码，每一页的密码不同，
 * 需要从这个密码本中寻找这样一个最长的密码，从它的末尾开始依次去掉一位得到的新密码也在密码本中存在。
 * 请输出符合该要求的密码，如果有多个符合要求的密码，则返回字典序最大的密码。若没有符合要求的密码，则返回空字符串。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String[] pwds = input.nextLine().split(" ");
        String ans = "";
        Set<String> all = new HashSet<>(Arrays.asList(pwds));
        for (String s : pwds) {
            if (check(s, all)) {
                if (s.length() > ans.length()) {
                    ans = s;
                } else if (s.length() == ans.length() && s.compareTo(ans) > 0) {
                    ans = s;
                }
            }
        }
        System.out.println(ans);
    }

    public static boolean check(String s, Set<String> all) {
        for (int i = 0; i < s.length(); i++) {
            if (!all.contains(s.substring(0, i + 1))) {
                return false;
            }
        }
        return true;
    }
}