首页 > 数据结构 > Hash表 > HDU 1113 Word Amalgamation-字符串处理-[解题报告] C++
2013
11-27

HDU 1113 Word Amalgamation-字符串处理-[解题报告] C++

Word Amalgamation

问题描述 :

In millions of newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble four words. Your task is to write a program that can unscramble words.

输入:

The input contains four parts:1. a dictionary, which consists of at least one and at most 100 words, one per line;
2. a line containing XXXXXX, which signals the end of the dictionary;
3. one or more scrambled `words’ that you must unscramble, each on a line by itself; and
4. another line containing XXXXXX, which signals the end of the file.

All words, including both dictionary words and scrambled words, consist only of lowercase English letters and will be at least one and at most six characters long. (Note that the sentinel XXXXXX contains uppercase X’s.) The dictionary is not necessarily in sorted order, but each word in the dictionary is unique.

输出:

For each scrambled word in the input, output an alphabetical list of all dictionary words that can be formed by rearranging the letters in the scrambled word. Each word in this list must appear on a line by itself. If the list is empty (because no dictionary words can be formed), output the line “NOT A VALID WORD” instead. In either case, output a line containing six asterisks to signal the end of the list.

样例输入:

tarp
given
score
refund
only
trap
work
earn
course
pepper
part
XXXXXX
resco
nfudre
aptr
sett
oresuc
XXXXXX

样例输出:

score
******
refund
******
part
tarp
trap
******
NOT A VALID WORD
******
course
******

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1113

题意:给一堆单词做字典,XXXXXX结束。然后给若干个单词,输出它和字典里哪些单词由同样的字母(个数也相同)组成,有多组的话按字典序输出。XXXXXX结束。

mark:题意有点绕。。。思路是先把字典里的单词排序,并且每个单词计算一个值val。这个val是把单词的字母排序以后hash得到的,范围是26^6也就是3亿多一点,可以用int来表示。这样接下来每个单词输入的时候,只要比对字典里的val,相同则可以输出。不hash的话就多存一个字母排序以后的单词也可以。

代码:

# include <stdio.h>
# include <string.h>
# include <stdlib.h>

typedef struct NODE{
    char str[10] ;
    int len, val ;
}NODE ;

NODE dp[110] ;

int scmp(const void *a, const void *b)
{
    return *(char*)a - *(char*)b ;
}

int calc(char *str, int len)
{
    int rtn = 0 ;
    qsort(str, len, 1, scmp) ;
    while (len--)
    {
        rtn = rtn * 27 + str[0] ;
        str++ ;
    }
    return rtn ;
}

int cmp( const void *a, const void *b)
{
    NODE *p = (NODE*)a, *q = (NODE*) b ;
    return strcmp(p->str, q->str) ;
}

int main ()
{
    int n, i = 0, flag ;
    char str[10] ;

    while (gets(str) && strcmp(str, "XXXXXX"))
    {
        strcpy (dp[i].str, str) ;
        dp[i].len = strlen(str) ;
        dp[i].val = calc(str, dp[i].len) ;
        i++ ;
    }
    n = i ;
    qsort(dp, n, sizeof(NODE), cmp) ;
    while (gets(str) && strcmp(str, "XXXXXX"))
    {
        flag = 0 ;
        for (i = 0 ; i < n ; i++)
        {
            if (strlen(str) == dp[i].len &&
                calc(str, dp[i].len) == dp[i].val)
            {
                puts (dp[i].str) ;
                flag = 1 ;
            }
        }
        if (flag == 0) puts ("NOT A VALID WORD") ;
        puts ("******") ;
    }
    return 0 ;
}

  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。