题目理解

题目要求我们找出输入文本中最大的5个变位词组（anagram groups）。变位词是指字母相同但排列顺序不同的单词，例如 "ate"、"eat"、"eta"、"tea" 属于同一个变位词组。每个变位词组的大小是该组中不同单词的数量。输出时需要按照组的大小降序排列，如果大小相同则按照组内字典序最小的单词升序排列。每组内的单词需要按字典序排列且不重复。

解题思路

1. 输入处理：读取所有单词，存储每个单词的原形式和排序后的形式（用于变位词判断）。
2. 变位词分组：将排序后形式相同的单词归为同一组。
3. 统计组信息：记录每组的起始位置、单词数量和字典序最小的单词。
4. 排序：按照组的大小降序排列，大小相同时按字典序最小的单词升序排列。
5. 输出：输出前5组，每组内的单词按字典序排列且不重复。 ##标程

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
using namespace std;

struct node//存放每个单词
{
    char s1[40];
    char s2[40];
} str[30005];

struct xu //存放每组相同字母异序词的信息
{
    int start;//在str数组中开始的位置
    int con;//数量
    char s[40];//组中字典序最小的单词
} Node[30005];
bool cmpw(node a,node b)
{
    if(strcmp(a.s2,b.s2)==0)
        return strcmp(a.s1,b.s1)<0;
    else
        return strcmp(a.s2,b.s2)<0;
}

bool cmp(xu a,xu b)
{
    if(a.con==b.con)
        return strcmp(a.s,b.s)<0;
    else
        return a.con>b.con;
}
int main()
{
    int n=0;
    while(~scanf("%s",str[n].s1))
    {
        int len=strlen(str[n].s1);
        strcpy(str[n].s2,str[n].s1);
        sort(str[n].s2,str[n].s2+len);//这里可以直接用sort非常方便！看了别人的代码是用桶排的
        n++;//统计单词个数
    }
    sort(str,str+n,cmpw);//按照字典序排序
    int m=1;//统计组数
    Node[0].start=0;
    Node[0].con=1;
    strcpy(Node[0].s,str[0].s1);//注意是将s1赋过去，因为前面已经按照字典序最小排序了，所以易知此为组中最小单词
    for(int i=1; i<n; i++)//遍历全部单词，统计共有多少不同的组
    {
        if(strcmp(str[i].s2,str[i-1].s2)==0)
            Node[m-1].con++;
        else
        {
            strcpy(Node[m].s,str[i].s1);
            Node[m].start=i;
            Node[m].con=1;
            m++;
        }
    }
    sort(Node,Node+m,cmp);//按照数量和字典序排序
    for(int i=0; i<5; i++)//输出前5组
    {
        int t=Node[i].start;
        if(i>=m)//不足5组全部输出后break；
        {
            printf("\n");
            break;
        }
        printf("Group of size %d:",Node[i].con);
        printf(" %s",str[t].s1);
        for(int j=1;j<Node[i].con;j++)
        {
            if(strcmp(str[t+j].s1,str[t+j-1].s1)==0)
                continue;
            printf(" %s",str[t+j].s1);
        }
        printf(" .\n");
    }
    return 0;
}

代码解析

1. 数据结构：

   • node 结构体：存储每个单词的原形式 s1 和排序后的形式 s2。
   • xu 结构体：存储每组变位词的起始位置 start、单词数量 con 和字典序最小的单词 s。

2. 输入处理：

   • 使用 scanf 读取单词，直到遇到 EOF。
   • 对每个单词的字母进行排序，生成排序后的形式 s2。

3. 变位词分组：

   • 对所有单词按 s2 排序，相同 s2 的单词会相邻。
   • 遍历排序后的单词数组，统计每组的大小和起始位置，记录字典序最小的单词。

4. 排序：

   • 对变位词组按大小降序排列，大小相同时按字典序最小的单词升序排列。

5. 输出：

   • 输出前5组，每组内的单词按字典序排列且去重。

示例分析

输入：

undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet

处理过程：

1. 对每个单词的字母排序，例如 "trace" 排序后为 "acert"。
2. 将排序后相同的单词归为一组：
   • "acert" 组：caret, carte, cater, crate, trace
   • "abet" 组：abet, bate, beat, beta
   • "aet" 组：ate, eat, eta, tea
   • 其他单词单独成组。
3. 按组的大小排序，输出前5组。

输出：

Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 1: displayed .
Group of size 1: singleton .

复杂度分析

• 时间复杂度：
  • 单词排序：O(n log n)，其中 n 是单词数量。
  • 变位词分组：O(n)。
  • 组排序：O(m log m)，其中 m 是组数。
• 空间复杂度：O(n)，存储所有单词和组信息。

总结

通过将每个单词的字母排序后进行分组，可以高效地找到所有变位词组。排序和分组的策略确保了算法的高效性和正确性，适用于大规模输入。