地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=1247

題目：

Hat’s Words

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13765????Accepted Submission(s): 4927

Problem Description A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.

?

Input Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.

?

Output Your output should contain all the hat’s words, one per line, in alphabetical order.

?

Sample Input a ahat hat hatword hziee word

?

Sample Output ahat hatword

?思路：1.用Trie樹，枚舉每個(gè)單詞，看他是否由兩個(gè)單詞組成，判斷過程其實(shí)就是字典樹的查找。時(shí)間復(fù)雜度是O（n*len）

　　　　2.map爆一發(fā)，map哈希的復(fù)雜度不清楚，不過也是枚舉每個(gè)單詞是否由兩個(gè)單詞組成，枚舉過程時(shí)間復(fù)雜度也是O（n*len），總體復(fù)雜度和Trie復(fù)雜度應(yīng)該差不多。

　　　　3.我看到我的運(yùn)行時(shí)間很短，可能暴力枚舉加map也能過。枚舉str[i]，str[j]，判斷map[str[i]+str[j]]存不存在即可，不知道能過否

代碼：

#include <stdio.h> #include <stdlib.h>using namespace std;#define MAXNUM 26 //定義字典樹結(jié)構(gòu)體 typedef struct Trie {bool flag;//從根到此是否為一個(gè)單詞Trie *next[MAXNUM]; }Trie; //聲明一個(gè)根 Trie *root; char ss[50006][100]; //初始化該根 void init() {root = (Trie *)malloc(sizeof(Trie));root->flag=false;for(int i=0;i<MAXNUM;i++)root->next[i]=NULL; } //對(duì)該字典樹的插入單詞操作 void insert(char *word) {Trie *tem = root;while(*word!='\0'){if(tem->next[*word-'a']==NULL){Trie *cur = (Trie *)malloc(sizeof(Trie));for(int i=0;i<MAXNUM;i++)cur->next[i]=NULL;cur->flag=false;tem->next[*word-'a']=cur;}tem = tem->next[*word-'a'];word++;}tem->flag=true; } bool search2(char *word) {Trie *tem = root;char *p=word;while(*p){if(tem==NULL||tem->next[*p-'a']==NULL)return false;tem=tem->next[*p-'a'];p++;}return tem->flag; } //查詢一個(gè)單詞的操作 bool search1(char *word) {Trie *tem = root;for(int i=0;word[i]!='\0';i++){tem=tem->next[word[i]-'a'];if(tem->flag&&search2(&word[i+1]))return 1;}return 0; }int main(void) {int n=1;init();while(~scanf("%s",ss[n]))insert(ss[n]),n++;for(int i=1;i<n;i++)if(search1(ss[i]))printf("%s\n",ss[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/weeping/p/5932318.html

總結(jié)

以上是生活随笔為你收集整理的hdu1247 Hat’s Words的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。