UVa11362 - Phone List (字典樹 詳解)

題目大意：

給你一組電話號碼，不超過 10 位數，如果這一組的電話號碼內只要有一個電話號碼是另外一個電話號碼的前綴就輸出 “NO”，否則就輸出 “YES”

分析：

這題用 字典樹 trie 解決是再好不過的了，我們先來介紹 trie！

trie 是一種有序樹，常用於搜尋提示，最好的比喻就是 google 的搜尋提示。就是你打幾個 key word 上去下面就跑出一堆你不想要的那個
這題為教學題，但此問題並沒有把 trie 的全部能力都展現出來，若以後我有其他題目可以將 trie 展現，我會再寫一篇做為說明，但此問題還有一點點的小設計，需要稍加解釋才能完全理解。
由於是寫給初學者看於是這題不使用任何 指標 pointer 來幫助這份程式碼，希望可以讓其他沒學過 C++ 的使用者都能學會。

TRIE 字典樹 原理

先看看圖片吧！這樣應該會比較有點概念

TRIE 本身也是一種樹，可以試著把它當作有規則的樹理解。畢竟他的發音跟 tree 根本沒有不一樣吧！
字串根據 TRIE 判斷，如果字串中的字元已經在 TRIE 擁有，則就在往 TRIE 的下一層判斷，假如沒有那我們就新增一個節點給予這個字元。

達到最後一層時則必須要有一個判斷表示這是某個單字的結尾。

QUESTION: TRIE 的時間複雜度呢？

新增字串的時間複雜度為 \(O(n)\)
搜尋的時間複雜度為 \(O(n)\)
搜尋關鍵字首的時間複雜度為 \(O(n)\)
算是還不錯用的資料結構之一，感覺學起來可以在很多地方用到，小弟我菜鳥還沒有實際用過

TRIE 字典樹的實現與說明

資料結構

struct node{
    bool isWord = false ; // 判斷是否為單字結尾
    int next[alp_MAXN]; // 到下個單字的索引，假如有 26 英文字母就設定 26
    // alp_MAXN = alphabet MAXN

    void reset(){ //重新設定
        for(int i = 0 ; i < alp_MAXN ; i++)
            next[i] = -1 ; 
        isWord = false ;
    }

}trie[arr_MAXN];

插入

void insrt(){
    int c , cur = 0; // c=字元的索引 cur = trie 現在這層，可以想像成樹的 root
    // cur =0，表示現在在 trie 的最一開始處
    for(int i = 0 ; i < strA.length() ; i++){ //將字串加入 trie
        c = strA[i] - '0' ;
        if(trie[cur].next[c] == -1 ){ //代表節點沒有被新增
            trie[cnt].reset(); //先重新設定節點，以免舊資料也加入
            trie[cur].next[c] = cnt ; //連接到下一層的 node
            cur = cnt++ ; //增加陣列長度
        }
        else{
            cur = trie[cur].next[c]; //因為已經有節點，可以直接往下層走就好
        }
    }
    trie[cur].isWord = true ; //由於已讀到字尾於是給他是字尾的標記
}

搜尋

跟插入的算法差不多，只是不需要新增節點的 if，只需要 else 跟最後判斷當已經讀到字尾時有沒有被標記成是字尾。

關鍵字查詢

跟搜尋一樣，但只要搜到此字串最底層後就可以 return 了，不需要檢查是否到字尾，如果是在寫題目通常是用 return true or false。

刪除

目前還沒有學到，隨後補上。打算要用遞迴嘗試創作看看，畢竟沒有用指標的 trie，在網路上的自學資源還很少見呢！XD

焦點回到題目上，解開題目的小設計

由於這題是問「前綴」，且只要一個就好，於是我們就用一個 flag 與一個 if 來進行判斷，只要當現在的電話號碼再依序插入 trie 中如果剛好字尾有被標記就表示已經有一個電話號碼已經是這個電話的前綴了就 return；另一個則是假如這個電話號碼字元已經全部被插入 trie 中表示，這組電話號碼是先前某個電話的前綴，所以也需要 return。

int flag = 0 ;
if(trie[cur].isWord || i == strA.length()-1 ) {flag = 1 ;return ;}

參考連結

Solution of UVa 11362-Phone List
[翻譯]資料結構——trie樹介紹
Trie

心得

應該是我這題選得不好，我原本是想要完整地把 trie 都學起來的，結果這題只需要用到 trie 的插入就好，刪除、搜尋都不需要用到，害我的心情很差：(，有種覺得沒有把全部資料都學起來的感覺，以後在挑選題目時需要謹慎挑選，要是挑到這種題目會覺得一個演算法沒有完整學習，有點小難過。

不過 trie 算是簡單易學的演算法，以自學來說。我就讀的大學演算法資源基本上是零，我都覺得我在這種環境下自學演算法可能也算是個抖 M 了吧XD，希望我在學習的路上能夠填補些自學的資源讓接下來想學習的人不要想我一樣這麼辛苦，我到現在才學有點太慢了呢，等我最近忙完後我再補上刪除的程式碼，補足自己的知識與空白之處。等學習完後看自己有沒有更多心得再補上。希望是有

題目程式碼

其實就是沒有附上說明的程式碼，我也花了兩個小時撰寫文章，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define alp_MAXN 15
#define arr_MAXN 1000009
using namespace std;
int cnt = 0 , flag = 0 ;
string strA ;

struct node{
    bool isWord = false ;
    int next[alp_MAXN];

    void reset(){
        for(int i = 0 ; i < alp_MAXN ; i++)
            next[i] = -1 ;
        isWord = false ;
    }

}trie[arr_MAXN];

void insrt(){
    int c , cur = 0;
    for(int i = 0 ; i < strA.length() ; i++){
        c = strA[i] - '0' ;
        if(trie[cur].next[c] == -1 ){
            trie[cnt].reset();
            trie[cur].next[c] = cnt ;
            cur = cnt++ ;
        }
        else{
            cur = trie[cur].next[c];
            if(trie[cur].isWord || i == strA.length()-1 ) {flag = 1 ;return ;}
        }
        if(flag) break ;
    }
    trie[cur].isWord = true ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    //freopen("out.txt" , "w" , stdout );
#endif // LOCAL

    int t , n ;
    cin >> t ;

    while(t--){
        cin >> n ;
        cnt = 1 ;
        flag = 0 ;
        trie[0].reset();
        for(int i = 0 ; i < n ; i++){
            cin >> strA ;
            insrt();
        }
        cout << (flag? "NO" : "YES") << '\n' ;

        //debug
//        for(int i = 0 ; i < 20 ; i++){
//            for(int j = 0 ; j < 10 ; j++)
//                cout << trie[i].next[j] << ' ' ;
//            cout << trie[i].isWord ;
//            cout << '\n' ;
//        }
    }

    return 0;
}