题面描述

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

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

请输出符合要求的密码，如果有多个符合要求的密码，则返回字典序最大的密码。

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

思路

为了找到满足条件的最长密码，并在长度相同的情况下选择字典序最大的密码，我们可以采取以下步骤：

1. 存储密码：将所有密码存入一个哈希集合中，以便快速查找。

2. 排序密码：按长度降序排序，如果长度相同，则按字典序降序排序。这样我们可以先检查较长的密码，且在长度相同的情况下优先检查字典序较大的密码。

3. 验证密码：对于每一个密码，逐步去掉末尾一位，检查得到的新密码是否存在于密码本中。如果所有子密码都存在，则该密码符合要求，返回它。

4. 优化处理：由于密码数量和长度都可能较大，需要优化存储和查找过程，使用高效的数据结构如 unordered_set 或 Trie。

代码分析

我们选择使用 C++ 的 unordered_set 来存储密码，以实现 O(1) 的查找时间。接着，我们将所有密码按照长度降序、字典序降序排序，这样在遍历时，第一找到的符合条件的密码即为所求。

具体步骤如下：

1. 读取输入，将所有密码存入一个向量 passwords。
2. 将密码存入 unordered_set 以便快速查找。
3. 对 passwords 进行排序，首先按长度降序，其次按字典序降序。
4. 遍历排序后的 passwords，对于每一个密码，逐步去掉末尾一位，检查剩余部分是否存在于 unordered_set 中。
5. 如果某个密码满足所有条件，则立即返回该密码。
6. 如果遍历完所有密码都没有找到符合条件的密码，则返回空字符串。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 读取整个输入为一行
    string line;
    getline(cin, line);
    // 使用字符串流分割单词
    vector<string> passwords;
    string word;
    // 使用 istringstream 进行分割
    istringstream iss(line);
    while(iss >> word){
        passwords.push_back(word);
    }
    // 使用 unordered_set 存储所有密码，便于快速查找
    unordered_set<string> password_set(passwords.begin(), passwords.end());
    // 按长度降序，长度相同则按字典序降序排序
    sort(passwords.begin(), passwords.end(), [&](const string &a, const string &b) -> bool{
        if(a.size() != b.size()) return a.size() > b.size();
        return a > b;
    });
    // 遍历排序后的密码，寻找符合条件的第一个
    string result = "";
    for(auto &pwd : passwords){
        bool valid = true;
        string current = pwd;
        while(!current.empty()){
            if(password_set.find(current) == password_set.end()){
                valid = false;
                break;
            }
            // 去掉末尾一位
            current.pop_back();
        }
        if(valid){
            result = pwd;
            break;
        }
    }
    cout << result;
} 

python

import sys

def main():
    # 提高输入输出效率
    # 在 Python 中，sys.stdin.read() 通常比 input() 更快，适合处理大规模数据
    input_data = sys.stdin.read()
    
    # 使用 split() 方法按空白字符分割输入，得到所有密码
    passwords = input_data.strip().split()
    
    # 使用集合存储所有密码，便于后续快速查找
    password_set = set(passwords)
    
    # 对密码列表进行排序：
    # 1. 首先按长度降序排列
    # 2. 长度相同的情况下，按字典序降序排列
    # 由于 Python 的 sort 是稳定的，先按字典序降序排序，再按长度降序排序
    # 这样可以确保在相同长度下，字典序较大的密码排在前面
    passwords_sorted = sorted(passwords, reverse=True)  # 先按字典序降序排序
    passwords_sorted.sort(key=lambda x: len(x), reverse=True)  # 再按长度降序排序
    
    result = ""  # 存储最终结果
    
    # 遍历排序后的密码列表，寻找第一个满足条件的密码
    for pwd in passwords_sorted:
        valid = True  # 标记当前密码是否满足条件
        current = pwd
        
        # 逐步去掉末尾一位，检查新密码是否存在于密码本中
        while current:
            if current not in password_set:
                valid = False  # 如果子密码不存在，标记为不满足条件
                break
            # 去掉末尾一位
            current = current[:-1]
        
        # 如果当前密码满足所有条件，则为结果，退出循环
        if valid:
            result = pwd
            break
    
    # 输出结果
    print(result)

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if(line == null || line.trim().isEmpty()){
            System.out.println("");
            return;
        }
        String[] passwords = line.trim().split("\\s+");
        Set<String> passwordSet = new HashSet<>(Arrays.asList(passwords));
        // 将密码列表转换为 List 并排序
        List<String> passwordList = new ArrayList<>(Arrays.asList(passwords));
        Collections.sort(passwordList, new Comparator<String>(){
            public int compare(String a, String b){
                if(a.length() != b.length()){
                    return b.length() - a.length(); // 长度降序
                }
                return b.compareTo(a); // 字典序降序
            }
        });
        String result = "";
        // 遍历排序后的密码，寻找符合条件的第一个
        for(String pwd : passwordList){
            boolean valid = true;
            String current = pwd;
            while(!current.isEmpty()){
                if(!passwordSet.contains(current)){
                    valid = false;
                    break;
                }
                current = current.substring(0, current.length()-1);
            }
            if(valid){
                result = pwd;
                break;
            }
        }
        System.out.println(result);
    }
}

题目内容

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

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

请输出符合要求的密码，如果有多个符合要求的密码，则返回字典序最大的密码。

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

输入描述

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

输出描述

一个字符串

备注

$1 ≤ 密码本的页数 ≤ 10^5$

$1 ≤ 每页密码的长度 ≤ 10^5$

样例1

输入

h he hel hell hello

输出

hello

说明

"$hello$"从末尾依次去掉一位得到的 $"hell"，"hel"，"he"$和$"h"$在密码本中都存在。

样例2

输入

b ereddred bw bww bwwl bwwlm bwwln

输出

bwwln

说明

$"bwwlm "$ 和 $"bwwln"$ 从末尾开始依次去掉一位得到密码在密码本中都存在。

但是 $"bwwln"$ 比 $"bwwlm"$ 字典序排序大，所以应该返回 $"bwwln"$