[アルゴリズム解答]白準5052電話番号リスト

今日解決した問題は白駿5052電話番号リスト私はtrieでこの問題を解決し、問題を解くと同時にtrieを整理し実現した.この内容はここです。本で確認できます!

質問する

電話番号のリストを表示します.この場合、リストが一致しているかどうかを判断するプログラムを作成します.
電話番号リストを一致させるには、1つの番号が別の番号の接頭辞であってはならない.
例えば、電話番号リストが次のような場合を考えてみましょう.

緊急電話:911

勤務:976259999

善英:91125426

このような状況では、善英に電話することはできない.ソンヨンが電話を取って、番号の3番目の位置を押した瞬間、緊急電話がかかってくるからだ.したがって、このリストは一致しないリストです.

入力

第1行は、試験例の個数tを与える.(1≦t≦50)各試験例の第1行には、電話番号の数nが与えられる.(1≦n≦10000)以下のn行には、リストに含まれる電話番号が与えられる.電話番号の長さは最大10桁で、リストの2つの電話番号が同じではない場合.

しゅつりょく

各テストケースについて,一致するリストであればYES,そうでなければNOを出力する.

例

入力します。

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

出力します。

NO
YES

解答方法

トライを利用して問題を解決した.したがって,まず所望の範囲内のシャドウを実現した.(Javaでtrigを実装するか、次のコードで実装するtrigを知りたい場合は、本明細書の上部リンクのtrigを参照してください!)
この問題はinsertのみが必要であるためinsertが実現され,問題の要求に従って他の番号のプレフィックスに番号を付けるとfalseが返される.ここで他の番号の接頭辞であるか否かを判断する基準は以下の2つである.

trieは番号付け中で、最後の数字ではなく、ある数字の最後の数字であれば

この場合、すでに含まれているある番号は、現在入れられている番号のプレフィックスです.

trieプラス後、最後の数字のノードに他のサブノードがある場合

この場合、現在入力されている番号は既にある番号のプレフィックスとなっている.

テストケースの数と各テストケースに含まれる数値に基づいて、入力値が正しい場合、数値を挿入してfalseを返すと、結果はNOになります.そうでなければ、datrueを返すと、結果はYES!

コード#コード#

package com.gowoon;

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static class Node{
        private Map<Character, Node> childNodes = new HashMap<>();
        private boolean isLast;
    }

    public static class Trie{
        private Node root;
        Trie(){
            this.root = new Node();
        }
        boolean insert(String number){
            Node node = this.root;
            for(int i=0; i<number.length(); i++){
                node = node.childNodes.computeIfAbsent(number.charAt(i), c -> new Node()); 
                if(node.isLast && i<number.length()-1) return false; 
            }
            if(!node.childNodes.isEmpty()) return false; 
            node.isLast = true;
            return true;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            boolean flag = true;
            Trie trie = new Trie();
            for(int j=0; j<n; j++){
                String number = br.readLine();
                if(flag){
                    if(!trie.insert(number)) flag = false;
                }
            }
            if(flag) bw.write("YES\n");
            else bw.write("NO\n");
            bw.flush();
        }

        bw.flush();
        bw.close();
        br.close();
    }
}