[BOJ]5052電話番号リスト

12020 ワード
アルゴリズム#アルゴリズム# 文字列 テキストリンク

问题的短片


に近づく


この問題を解くことで、初めてTrieの資料構造を知りました.Treeは文字列を効率的にツリーに格納し、検索文字列はO(L=文字列の長さ)のみを必要とします.

各ノードの子供には、ルートノードからノードへの文字列の接頭辞があります.
#include <bits/stdc++.h>
using namespace std;

#define NUMBER 10
#define MAX 10000

struct Trie {
  bool is_terminal;
  Trie *children[NUMBER];

  Trie(): is_terminal(false) {
    memset(children, 0, sizeof(children));
  }

  ~Trie() {
    for(int i = 0; i < NUMBER; i++) {
      if(children[i])
        delete children[i];
    }
  }

  void insert(char *key) {
    if(*key == '\0') {
      is_terminal = true;
      return;
    }

    int idx = *key - '0';
    if(children[idx] == 0)
      children[idx] = new Trie();

    children[idx]->insert(key + 1);
  }

  bool find(char *key) {
    if(*key == '\0')
      return true;

    if(is_terminal)
      return false;

    int idx = *key - '0';
    return children[idx]->find(key + 1);
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  int T, N;
  char tmp[MAX][11];
  bool inconsistent;
  Trie *ptr;

  cin >> T;
  for(int i = 0; i < T; i++) {
    cin >> N;
    ptr = new Trie();
    inconsistent = false;

    for(int j = 0; j < N; j++) {
      cin >> tmp[j];
      ptr->insert(tmp[j]);
    }

    for(int j = 0; j < N; j++) {
      if(!ptr->find(tmp[j])) {
        inconsistent = true;
        break;
      }
    }

    delete ptr;

    if(inconsistent)
      cout << "NO" << endl;
    else
      cout << "YES" << endl;
  }
}
[BOJ]伯俊1110-プラスサイクル
[Python] TIL 03