题解 | #手机号码#

没学过trie树的小白来写一篇题解,感谢各位大佬指点。

1、计算操作：先计算出长度为n共有多少种用ans记录,然后减去开头为输入的电话号码的个数 2、去重处理：避免重复减去有包含关系的号码

```#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
int n,m;
bool cmp(string a,string b){
    return a.length()<b.length();
}
signed main()
{
//以下为输入操作
    cin>>n>>m;
    ll ans=1;
// 计算所有可能的电话号码总数：10^n
    for(int i=0;i<n;++i){
        ans*=10;
    }
    vector<string> srr(m);
    for(int i=0;i<m;++i)cin>>srr[i];
//以下为逻辑操作
    sort(srr.begin(),srr.end(),cmp);//把字符串从短到长排序
    vector<string> ss;
    for(int i=0;i<m;++i){
        bool f=false;
        for(const auto& str :ss){
            if(srr[i].length()>=str.length()&&srr[i].substr(0,str.length())==str){// 如果srr[i]以str开头
                f=true;
                break;
            }
        }
        if(!f){
            ss.push_back(srr[i]);
        }
    }

    for(int i=0;i<(int)ss.size();++i){
        int len=ss[i].length();
        int t=n-len;
        ll a=1;
// 计算以该前缀开头的号码数量：10^(n-len)
        for(int k=0;k<t;++k){
            a*=10;
        }
        ans-=a;
    }
    cout<<ans;
    return 0;
}