首页 > 代码库 > HDU1247 Hat’s Words 【trie树】
HDU1247 Hat’s Words 【trie树】
Hat’s Words
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7502 Accepted Submission(s): 2705
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.
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.
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
这题开始总想着走捷径,想根据trie树内部节点将单词分成前后缀,前缀一定在树里,所以只需判断后缀是否在树里,但是很多细节很棘手,比如怎样确定后缀,后缀怎样检索,怎样在一个单词内改变前后缀等,折腾了很久,实在没法解决,然后就用了一开始就很鄙夷的方法,将每个字符串都存到数组并插入到树里,然后将每个字符串遍历拆分成前后缀,再检索前后缀是否都在树中。这题再次验证了一个道理,就是在没有想出更好的方法之前,最笨的方法就是最好的方法。
#include <stdio.h> #include <string.h> #include <stdlib.h> struct Node{ struct Node *next[26]; int wordCover; }; Node *root = (Node *)malloc(sizeof(Node)); char suffix[50], prefix[50], strArr[50000][50]; void cleanStruct(Node *p) { memset(p->next, 0, sizeof(p->next)); p->wordCover = 0; } void insert(char *str) { int id; Node *p = root; while(*str) { id = *str - 'a'; if(p->next[id] == NULL){ p->next[id] = (Node *)malloc(sizeof(Node)); cleanStruct(p->next[id]); } p = p->next[id]; ++str; } ++p->wordCover; } int isExist(char *str) { Node *p = root; int id; while(*str){ id = *str - 'a'; if(p->next[id] == NULL) return 0; p = p->next[id]; ++str; } return p->wordCover; } void deleteTrie(Node *p) { for(int i = 0; i < 26; ++i) if(p->next[i]) deleteTrie(p->next[i]); free(p); } int main() { //freopen("stdin.txt", "r", stdin); int id = 0, i, j, len; cleanStruct(root); while(gets(strArr[id])) insert(strArr[id++]); for(i = 0; i < id; ++i){ len = strlen(strArr[i]); for(j = 1; j < len; ++j){ strcpy(prefix, strArr[i]); prefix[j] = '\0'; strcpy(suffix, strArr[i] + j); if(isExist(prefix) && isExist(suffix)){ puts(strArr[i]); break; } } } deleteTrie(root); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。