題目:
Phone List |
| Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 235 Accepted Submission(s): 92 |
Problem Description 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: 1. Emergency 911 2. Alice 97 625 999 3. Bob 91 12 54 26 In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent. |
Input The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits. |
Output For each test case, output “YES” if the list is consistent, or “NO” otherwise. |
Sample Input 2
3
911
97625999
91125426
5
113
12340
123440
12345
98346 |
Sample Output NO
YES |
Source 2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest - Warm Up（3） |
Recommend lcy |
題目分析：
這道題，屬于Trie的入門級別的題目。但是在這里先介紹1下不用Trie怎樣解決這道題。在1堆號碼中,
要判斷1個號碼是不是是其他號碼的前綴。我們可以先對這對號碼按字典序進行1下排序。然后順次判斷相鄰兩個號碼中是不是有號碼是其它號碼的前綴便可。整體的時間復雜度要比暴力做法的O(n^2)要好很多。
這里還需要介紹1下的是strncmp這個函數。
strncmp(): 這個函數用來比較s1和s2字符串，這個函數將返回1個值， 它的符號與第1對不同的字符的比較結果相干。如果兩個字符串相等的話，strncmp將返回0。如果s1是s2的1個子串的話，s1小于s2。另外還有，函數 int strncmp (const char *s1, const char *s2, size_t size) 此函數與strcmp極其類似。不同的地方是，strncmp函數是指定比較size個字符。也就是說，如果字符串s1與s2的前size個字符相同，函數返回值為0。
代碼以下：
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
