给你一串数字(≤12个),每个数字可以对应3个字母,求生成的所有字符串里,在字典内的有哪些。
我做的时候想的是字典树(Trie 树),模拟数串生成的所有字符串,然后在字典树里查找一下。
/*
TASK:namenum
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
#define MAX 26
#define N 5001
#define M 15
using namespace std;
int top,trie[N*M][MAX+1];
int search(char s[]){
int i,rt;
for(rt=0,i=0;rt=trie[rt][s[i]-'A'];)
if(!s[++i])return trie[rt][MAX];
return 0;
}
void insert(char s[]){
int rt=0;
for(int i=0;s[i];i++){
int &nxt=trie[rt][s[i]-'A'];
if(0==nxt) nxt=++top;
rt=nxt;
}
trie[rt][MAX]=1;
}
int cnt;
//虽然只有3个字母,但是后面有\0,故要开到4。
char ma[12][4]={"","","ABC","DEF","GHI","JKL","MNO","PRS","TUV","WXY"};
char s[M],name[M];
int dfs(int d){
if(!s[d]){
if(search(name)){
cout<<name<<endl;
return 1;
}
return 0;
}
int ok=0;
for(int i=0;i<3;i++){
name[d]=ma[s[d]-'0'][i];
if(dfs(d+1))ok=1;
}
return ok;
}
int main() {
//freopen("namenum.in","r",stdin);
//freopen("namenum.out","w",stdout);
ifstream in("dict.txt");
while(in>>s)insert(s);
cin>>s;
if(!dfs(0))cout<<"NONE"<<endl;
return 0;
}
官方题解里说可以二分,还可以把字典全部转为数字,总共就5000个,这就是逆向思维。
/*
TASK:namenum
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
#define MAX 26
#define N 5001
#define M 15
using namespace std;
char dic[N][M];
int ma[MAX]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9};
ll num[N],tot,t;
int main() {
freopen("namenum.in","r",stdin);
freopen("namenum.out","w",stdout);
ifstream in("dict.txt");
while(in>>dic[tot]){
ll &ans=num[tot];
for(int i=0;dic[tot][i];i++)
ans=ans*10+ma[dic[tot][i]-'A'];
tot++;
}
cin>>t;
int ok=0;
for(int i=0;i<tot;i++)
if(num[i]==t){ok=1;cout<<dic[i]<<endl;}
if(!ok)cout<<"NONE"<<endl;
return 0;
}
原文链接: https://www.cnblogs.com/flipped/p/5850652.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/240126
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!