題目描述

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

段落大意:給定一組電話號碼，判斷它們是否一致，即沒有一個號碼是另一個號碼的前綴。假設電話目錄列出了以下號碼：

Emergency 911

Alice 97 625 999

Bob 91 12 54 26

In the case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialed the first three digits of bob’s phone number. So this list would not be sonsistent.

段落大意:在這種情況下，不可能撥打Bob的電話，因為只要你撥打Bob電話號碼的前三位，中心就會立即將你的呼叫轉接到緊急線。因此，這個列表就不一致。

輸入

The first line of input gives a single integer, 1<=t<=40, the number of test cases. Each test starts with n, the number of phone numbers, on a separate line, 1<=n<=10000. Then follows n linss with one unique phone numbers on each line. A phone number is a sequence of at most ten digits.

段落大意:第一行輸入一個整數(shù)，1<=t<=40，表示測試用例的數(shù)量。每個測試用例以一個單獨的行n開始，表示電話號碼的數(shù)量，1<=n<=10000。然后是n行，每行包含一個唯一的電話號碼。電話號碼是最多包含十位數(shù)字的序列。

輸出

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

段落大意:對于每個測試用例，如果列表一致，則輸出“YES”，否則輸出“NO”

輸入樣例 1?

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

輸出樣例 1

NO
YES

實現(xiàn)

本題采用Trie樹思路文章來源地址http://www.zghlxwxcb.cn/news/detail-814502.html

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_PHONE_LENGTH 11
typedef struct TrieNode {
    struct TrieNode* children[10];
    int isEndOfWord;
} TrieNode;
TrieNode* createTrieNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    for (int i = 0; i < 10; ++i) {
        node->children[i] = NULL;
    }
    node->isEndOfWord = 0;
    return node;
}
int insertPhoneNumber(TrieNode* root, const char* phoneNumber) {
    TrieNode* current = root;
    for (int i = 0; i < strlen(phoneNumber); ++i) {
        int index = phoneNumber[i] - '0';
        if (current->children[index] == NULL) {
            current->children[index] = createTrieNode();
        }
        current = current->children[index];
        if (current->isEndOfWord) {
            return 0;
        }
    }
    current->isEndOfWord = 1;
    for (int i = 0; i < 10; ++i) {
        if (current->children[i] != NULL) {
            return 0;
        }
    }
    return 1;
}
void freeTrie(TrieNode* root) {
    if (root == NULL) return;
    for (int i = 0; i < 10; ++i) {
        freeTrie(root->children[i]);
    }
    free(root);
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        TrieNode* root = createTrieNode();
        int consistent = 1;
        for (int i = 0; i < n; ++i) {
            char phoneNumber[MAX_PHONE_LENGTH];
            scanf("%s", phoneNumber);
            if (!consistent) {
                continue;
            }
            consistent = insertPhoneNumber(root, phoneNumber);
        }
        printf("%s\n",consistent?"YES":"NO");
        freeTrie(root);
    }
    return 0;
}

到了這里，關于數(shù)據(jù)結構編程題:Phone List的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！