HDU-4287-Intelligent IME

HDU-4287-Intelligent IME
 
http://acm.hdu.edu.cn/showproblem.php?pid=4287
 
開始用字典樹+深搜，超時。。。。後來發現題目最多6位數，可將字符串轉化成對應的數字，然後hash即可
 
TLE的代碼
 
 
[cpp] 
#include<iostream>   
#include<cstdio>   
#include<cstring>   
#include<cstdlib>   
using namespace std;   
int n,m,ans; 
char map[5005][8]; 
char word[8]; 
char phone[8][4]={{0,1,2},{3,4,5},{6,7,8},{9,10,11},{12,13,14},{15,16,17,18},{19,20,21},{22,23,24,25}};  
int  num[8]={3,3,3,3,3,4,3,4}; 
struct node   
{   
    int count;   
    node *childs[26];    
    node()   
    {   
        count=0;   
        for(int i=0;i<26;i++)   
        childs[i]=NULL;   
    }   
};   
node *root;   
node *current,*newnode;  
void insert(char *str) //插入字符串   
{   
    int i,m;   
    current=root;   
    for(i=0;i<strlen(str);i++)   
    {   
        m=str[i]-'a';   
        if(current->childs[m]!=NULL)   
        current=current->childs[m];   
        else   
        {   
            newnode=new node;   
            current->childs[m]=newnode;   
            current=newnode;   
        }   
    }   
    current->count=1; 
} 
int search(char *str)   //在字典樹中查找一個單詞是否存在   
{   
    int i,m;   
    current=root;   
    for(i=0;i<strlen(str);i++)   
    {   
        m=str[i]-'a';   
        if(current->childs[m]==NULL)   
        return 0;   
        current=current->childs[m];   
    }   
    return current->count;   
}   
void del(node *head)     
{   
    int i;   
    for(i=0;i<26;i++)   
    if(head->childs[i]!=NULL)    
    del(head->childs[i]);   
    delete(head);   
} 
void dfs(char str[10],int len,int t) 
{ 
    int i,s; 
    if(t==len) 
    { 
        word[len]='\0'; 
        if(search(word)) 
        ans++; 
    } 
    s=num[str[t]-'2']; 
    for(i=0;i<s;i++) 
    { 
        word[t]=phone[str[t]-'2'][i]+'a'; 
        dfs(str,len,t+1); 
    } 
} 
int main() 
{ 
    int t,i; 
    int len; 
    char temp[8]; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d%d",&n,&m); 
        for(i=0;i<n;i++) 
        scanf("%s",map[i]); 
        root=new node; 
        while(m--) 
        { 
            scanf("%s",temp); 
            insert(temp); 
        } 
        for(i=0;i<n;i++) 
        { 
            ans=0; 
            len=strlen(map[i]); 
            dfs(map[i],len,0); 
            printf("%d\n",ans); 
        } 
        del(root); 
    } 
    return 0; 
} 
AC的代碼
 
[cpp]
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
int hashh[1000005]; 
int a[5005]; 
char str[10]; 
int judge(char c) 
{ 
    if('a'<=c&&c<='c') 
    return 2; 
    else if('d'<=c&&c<='f') 
    return 3; 
    else if('g'<=c&&c<='i') 
    return 4; 
    else if('j'<=c&&c<='l') 
    return 5; 
    else if('m'<=c&&c<='o') 
    return 6; 
    else if('p'<=c&&c<='s') 
    return 7; 
    else if('t'<=c&&c<='v') 
    return 8; 
    else if('w'<=c&&c<='z') 
    return 9; 
} 
int main() 
{ 
    int t; 
    int i,j,n,m,len,sum; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d%d",&n,&m); 
        for(i=0;i<n;i++) 
        scanf("%d",&a[i]); 
        memset(hashh,0,sizeof(hashh)); 
        for(i=1;i<=m;i++) 
        {  www.2cto.com
            scanf("%s",str); 
            len=strlen(str); 
            sum=0; 
            for(j=0;j<len;j++) 
            sum=sum*10+judge(str[j]); 
            hashh[sum]++; 
        } 
        for(i=0;i<n;i++) 
        printf("%d\n",hashh[a[i]]); 
    } 
    return 0; 
}