
蒜头君作为蒜厂的工程师,在开发网站时不小心写出了一个 Bug:当用户输入密码时,如果既和自己的密码一致,也同时是另一个用户密码的 前缀 时,用户会跳转到 404 页。
然而蒜头君坚称:我们的用户那么少,怎么可能触发这个 Bug……
机智的你,能不能帮蒜头君确认一下这个 Bug 到底会不会触发呢?
输入格式
第一行输入一个整数 $n(1 \leq n \leq 233333)$,表示蒜厂网站的用户数。接下来一共 $n$ 行,每行一个由小写字母 a-z
组成的字符串,长度不超过 $10$,表示每个用户的密码。蒜厂的数据库容量太小,所有密码长度加起来小于 $466666$。
输出格式
如果触发了 Bug 则输出一行 Bug!
,否则输出一行 Good Luck!
。
样例 1
3 abc abcdef cdef
Bug!
样例2
3 abc bcd cde
Good Luck!
这题就是最单纯的前缀树模板。
对于先输入短的,后输入长的,就在遇到长的密码的每一个结点判断是不是 isEnd()
,反之,则在 setEnd()
之后检查还有没有后面的孩子结点。
import java.util.HashMap; import java.util.Scanner; public class Main { static Scanner in = new Scanner(System.in); public static void main(String[] args) { Trie tree = new Trie(); int n = in.nextInt(); for (int i = 0; i < n; i++) { String s = in.next(); try { tree.insert(s); } catch (Exception e) { System.out.println("Bug!"); System.exit(0); } } System.out.println("Good Luck!"); } } class Trie { private TrieNode root; /** * Initialize your data structure here. */ public Trie() { root = new TrieNode(); } /** * Inserts a word into the trie. */ public void insert(String word) throws Exception { TrieNode node = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (!node.contains(c)) { node.put(c); } node = node.get(c); if (node.isEnd()) { throw new Exception("BUG"); } } node.setEnd(); if (node.hasChild()) { throw new Exception("BUG"); } } } class TrieNode { private HashMap<Character, TrieNode> links; private boolean end; public TrieNode() { links = new HashMap<>(); end = false; } public boolean isEnd() { return end; } public void setEnd() { end = true; } public TrieNode get(char c) { return links.get(c); } public void put(char c) { links.put(c, new TrieNode()); } public boolean contains(char c) { return links.containsKey(c); } public boolean hasChild() { return !links.keySet().isEmpty(); } }