LIKE CODING: MJ [42] Find area code

LIKE CODING: MJ [42] Find area code

MJ [42] Find area code

Question:
+1 North America
...
+1950 Northern Cal
….1point3acres缃�
+44 UK. 1point 3acres 璁哄潧
+4420 London-google 1point3acres
+447 UK Mobile
+44750 Vodafoned. From 1point 3acres bbs
…

and we have a phone number, for instance
+447507439854795-google 1point3acres
+44989045454
. from: 1point3acres.com/bbs 
return where the number is from

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=101580&ctid=92

对,是字典树. 选字典的原因是号码总体的长度很小, 所以树的高度不高. 建树很简单啊. 就是从第一个字符(数字)开始扫, 然后把同类的加在一起. 比如.鐣欏璁哄潧-涓€浜�-涓夊垎鍦� +44 UK +4420 London +447 UK Mobile +44750 Vodafoned 要是题是这么给的, 已经很明显提示你要用字典树了. 1point 3acres 璁哄潧 这4个是 root -> 4->4 root -> 4->4->2->0. from: 1point3acres.com/bbs  root -> 4->4->7 root -> 4->4->7->5->0. 1p

class TrieNode{

public:

    char key;

    bool isLeaf = false;

    TrieNode *children[10] = {NULL};

    TrieNode(){}

    TrieNode(char k):key(k){}

};

 

class Solution{

    TrieNode * root = new TrieNode();

    void insert(string s){

        TrieNode *p = root;

        for(auto c:s){

            if(p->children[c-'0']==NULL){

                p->children[c-'0'] = new TrieNode(c);

            }

            p = p->children[c-'0'];

        }

        p->isLeaf = true;

    }

    unordered_map<string, string> areacode;

public:

    Solution(){

        areacode["1"] = "North America";

        areacode["1950"] = "Northern Cal";

        areacode["44"] = "UK";

        areacode["447"] = "UK Mobile";

        areacode["4420"] = "London";

        areacode["44750"] = "Vodafoned";

        for(auto ac:areacode){

            insert(ac.first);

        }

    }

    string findArea(string number){

        string addr, cur;

        TrieNode *p = root;

        for(auto c:number){

            if(p->children[c-'0']){

                p = p->children[c-'0'];

                cur += c;

                if(p->isLeaf) addr += "::"+areacode[cur];

            }else{

                break;

            }

        }

        return addr;

    }

};

 

int main(){

  Solution sol;

  cout<<sol.findArea("447507439854795")<<endl;

  return 0;

}

Read full article from LIKE CODING: MJ [42] Find area code