hdu 1247 Hat’s Words(字典树)

简介:

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1247

分析:这道题可以使用stl中的map直接来解决,也可以使用字典树来解决,当然字典树的效率会更高

(1)stl解法不做过多的解释,这里有网上一个stl解法的链接  http://hi.baidu.com/mingyiyiyi_3/item/25835459866641494eff20f5

(2)字典树解法,字典树 (详细看链接解释)

定义一个字典树结构体

typedef struct Trie
{
    bool flag;//从根到此是否为一个单词
    Trie *next[MAXNUM];
}Trie;

字典树的插入操作
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;
}

以上两段代码是字典树的核心,要先弄懂。然后针对本题,flag是标志从根到当前位置是否可以组成一个单词,是为true,否为false。然后搜索每个单词是否有两个单词组成,这时就要把每个单词拆分,一个长度为n的单词可以拆分为n-1组组合,然后枚举判断是否在该字典树集合内。

 

复制代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXNUM 26
using namespace std;

//单词
char words[50005][100];
//定义字典树
typedef struct Trie
{
    bool flag;//从根到此是否为一个单词
    Trie *next[MAXNUM];
}Trie;

Trie *root;

void init()
{
    root = (Trie *)malloc(sizeof(Trie));
    root->flag=false;
    for(int i=0;i<MAXNUM;i++)
    root->next[i]=NULL;
}

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 search(char *word)
{
    Trie *tem = root;
    for(int i=0;word[i]!='\0';i++)
    {
        if(tem==NULL||tem->next[word[i]-'a']==NULL)
        return false;
        tem=tem->next[word[i]-'a'];
    }
    return tem->flag;
}


int main()
{
    init();
    int t=0;
    char w[100];
    while(scanf("%s",words[t])!=EOF)
    {

        insert(words[t]);
        t++;
    }
    for(int i=0;i<t;i++)
    {
        memset(w,'\0',sizeof(w));
        for(int j=0;words[i][j]!='\0';j++)
        {
            *(w+j)=*(words[i]+j);
            if(search(w)&&search((words[i]+j+1)))
            {
                printf("%s\n",words[i]);
                break;
            }
        }

    }
    return 0;
}
复制代码
相关文章
|
5月前
【洛谷 P2249】【深基13.例1】查找(向量+lower_bound)
**深基13.例1**是关于查找的编程题,要求在单调不减的整数序列中,对每个查询\( q \)返回其首次出现的位置或输出\-1。输入包含序列大小\( n \),查询次数\( m \),以及序列和查询列表。使用`lower_bound`进行二分查找,找到第一个大于等于目标值的元素位置,若找不到或找到的值不等于目标值,则返回\-1。提供的AC代码中,优化了输入读取,并利用`std::vector`和`std::lower_bound`实现了高效解决方案。
34 0
UVa10776 - Determine The Combination(有重复元素的组合问题)
UVa10776 - Determine The Combination(有重复元素的组合问题)
43 0
|
算法 Python
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 389. Find the Difference
给定两个字符串 s 和 t,它们只包含小写字母。 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。 请找出在 t 中被添加的字母。
115 0
LeetCode 389. Find the Difference
[HDU7073] Integers Have Friends 2.0 -随机大法好
题意: 找到最大的一个集合,使得集合内所有元素 % m(>=2) 问最大的集合大小
94 0
[HDU7073] Integers Have Friends 2.0 -随机大法好
LeetCode之Find the Difference
LeetCode之Find the Difference
118 0