首页 > 其他分享 >49. 字母异位词分组

49. 字母异位词分组

时间:2024-06-04 21:03:58浏览次数:26  
标签:49 int 异位 returnSize st char 分组 str 字符串

题目

给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

代码

完整代码

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

// 定义一个结构体来存储字符串及其相关信息
typedef struct {
    char* str;        // 排序后的字符串
    char* oldstr;     // 原始字符串
    int len;          // 字符串长度
    int isGrouped;    // 是否已分组
    int indexInRes;   // 在结果数组中的索引
} str_t;

// 用于根据字符串长度排序的比较函数
int cmp1(const void* a, const void* b) {
    return ((str_t*)a)->len - ((str_t*)b)->len;
}

// 用于对字符串中的字符排序的比较函数
int cmp2(const void* a, const void* b) {
    return (*(char*)a) - (*(char*)b);
}

// 主函数,用于分组字母异位词
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    str_t str_st[10000] = {0};  // 存储字符串及其信息的结构体数组
    char ***res = (char***)malloc(sizeof(char**) * strsSize); // 结果数组
    *returnColumnSizes = (int*)malloc(sizeof(int) * strsSize); // 每个组的大小数组
    *returnSize = 0; // 初始组数为0

    // 初始化结果数组和列大小数组
    for (int i = 0; i < strsSize; i++) {
        res[i] = (char**)malloc(sizeof(char*) * strsSize);
        (*returnColumnSizes)[i] = 0;
    }
    
    // 处理输入字符串,将其排序并存储在结构体数组中
    for (int i = 0; i < strsSize; i++) {
        str_st[i].oldstr = strs[i];
        str_st[i].len = strlen(strs[i]);
        str_st[i].str = strdup(strs[i]);
        qsort(str_st[i].str, str_st[i].len, sizeof(char), cmp2);
    }
    // 根据字符串长度对结构体数组进行排序
    qsort(str_st, strsSize, sizeof(str_t), cmp1);

    // 分组字母异位词
    for (int i = 0; i < strsSize; i++) {
        if (!str_st[i].isGrouped) { // 如果当前字符串没有被分组
            str_st[i].indexInRes = *returnSize;
            res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[i].oldstr;
            str_st[i].isGrouped = 1;
            for (int j = i + 1; j < strsSize; j++) {
                if (strcmp(str_st[i].str, str_st[j].str) == 0) {
                    res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[j].oldstr;
                    str_st[j].isGrouped = 1;
                }
            }
            (*returnSize)++;
        }
    }
    
    return res;
}

// 主函数测试
int main() {
    char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    int strsSize = 6;
    int returnSize;
    int *returnColumnSizes;

    char ***result = groupAnagrams(strs, strsSize, &returnSize, &returnColumnSizes);

    for (int i = 0; i < returnSize; i++) {
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%s ", result[i][j]);
        }
        printf("\n");
    }

    // 释放内存
    for (int i = 0; i < returnSize; i++) {
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);

    return 0;
}

思路分析

题目要求将字母异位词组合在一起。字母异位词是指由相同字母组成但顺序不同的字符串。我们可以通过对每个字符串进行排序,使其相同字母的字符串能够变得相等。然后根据排序后的字符串进行分组。
(写完才发现好像不用排序len,,,反正都要遍历,然后看isgrouped…

拆解分析

  1. 结构体定义:

    • str_t结构体用于存储原始字符串、排序后的字符串、长度、是否已分组标志以及在结果数组中的索引。
  2. 比较函数:

    • cmp1:用于根据长度排序。
    • cmp2:用于字符串排序。
  3. 内存分配:

    • 动态分配结果数组 res 和每个组大小的数组 returnColumnSizes
  4. 字符串处理和排序:

    • 对每个字符串进行排序,并按长度排序 str_st 数组。
  5. 分组逻辑:

    • 遍历字符串数组,根据排序后的字符串相等性进行分组,并更新 returnSizereturnColumnSizes

详细拆解

  1. 初始化数据结构:

    str_t str_st[10000] = {0};  // 存储字符串及其信息的结构体数组
    char ***res = (char***)malloc(sizeof(char**) * strsSize); // 结果数组
    *returnColumnSizes = (int*)malloc(sizeof(int) * strsSize); // 每个组的大小数组
    *returnSize = 0; // 初始组数为0
    
  2. 为每个组初始化结果数组和列大小数组:

    for (int i = 0; i < strsSize; i++) {
        res[i] = (char**)malloc(sizeof(char*) * strsSize);
        (*returnColumnSizes)[i] = 0;
    }
    
  3. 处理输入字符串,将其排序并存储在结构体数组中:

    for (int i = 0; i < strsSize; i++) {
        str_st[i].oldstr = strs[i];
        str_st[i].len = strlen(strs[i]);
        str_st[i].str = strdup(strs[i]);
        qsort(str_st[i].str, str_st[i].len, sizeof(char), cmp2);
    }
    
  4. 根据字符串长度对结构体数组进行排序:

    qsort(str_st, strsSize, sizeof(str_t), cmp1);
    
  5. 分组字母异位词:

    for (int i = 0; i < strsSize; i++) {
        if (!str_st[i].isGrouped) { // 如果当前字符串没有被分组
            str_st[i].indexInRes = *returnSize;
            res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[i].oldstr;
            str_st[i].isGrouped = 1;
            for (int j = i + 1; j < strsSize; j++) {
                if (strcmp(str_st[i].str, str_st[j].str) == 0) {
                    res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[j].oldstr;
                    str_st[j].isGrouped = 1;
                }
            }
            (*returnSize)++;
        }
    }
    
  6. 主函数测试:

    int main() {
        char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
        int strsSize = 6;
        int returnSize;
        int *returnColumnSizes;
    
        char ***result = groupAnagrams(strs, strsSize, &returnSize, &returnColumnSizes);
    
        for (int i = 0; i < returnSize; i++) {
            for (int j = 0; j < returnColumnSizes[i]; j++) {
                printf("%s ", result[i][j]);
            }
            printf("\n");
        }
    
        // 释放内存
        for (int i = 0; i < returnSize; i++) {
            free(result[i]);
        }
        free(result);
        free(returnColumnSizes);
    
        return 0;
    }
    

复杂度分析

  • 时间复杂度:

    • 对每个字符串排序的时间复杂度为 O(N log N),其中 N 为字符串长度。
    • 对结构体数组进行排序的时间复杂度为 O(M log M),其中 M 为字符串数组的大小。
    • 总时间复杂度为 O(M * N log N),M 是字符串数组的大小,N 是最长字符串的长度。
  • 空间复杂度:

    • 主要由存储结果的二维数组 res 和辅助数组 str_st 组成。总体空间复杂度为 O(M * N)。

结果

结果

标签:49,int,异位,returnSize,st,char,分组,str,字符串
From: https://blog.csdn.net/qq_35085273/article/details/139453588

相关文章

  • Codeforces Round 949 (Div. 2) 中文题解
    A对于一个特定的\(x\),Piggy总是会选择\(p\)使得\(p\)是质数,所以分数就是\(x\)的质因子个数。容易发现至少有\(t\)个质因子的数是\(2^t\)。最大的满足\(2^t\ler\)的整数\(t\)是\(\left\lfloor\log_2r\right\rfloor\)。又因为\(2l\ler\),所以\(\log_2l+......
  • 【数据分享】中国民政统计年鉴(1949-2022)
    大家好!今天我要向大家介绍一份重要的中国民政统计数据资源——《中国民政统计年鉴》。这份年鉴涵盖了从1949年到2022年中国民政统计全面数据,并提供限时免费下载。(无需分享朋友圈即可获取)数据介绍从1949年到2022年,每年的《中国民政统计年鉴》不仅是数据记录的集合,更是我国社会......
  • 力扣-494. 目标和
    1.题目题目地址(494.目标和-力扣(LeetCode))https://leetcode.cn/problems/target-sum/题目描述给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加 '+'或'-',然后串联起所有整数,可以构造一个表达式:例如,nums=[2,1],可以在2之前添加'+',......
  • FuTalk设计周刊-Vol.049
    #AI漫谈热点捕手1.GeminiPro1.5及其百万上下文功能现已向所有人开放GeminiPro1.5加入视频模态的长上下文功能,AI可以处理更复杂的视频内容。链接https://aistudio.google.com/app/prompts/new_chat?ref=top.aibase.com2.Figma2024Config大会6月26-27日今年的Conf......
  • 【大数据】Hadoop集群搭建(8249字)
    文章目录@[toc]NAT配置IP配置SecureCRT配置PropertiesTerminalEmulationAppearanceJava安装环境变量配置Hadoop1.0安装建立临时文件夹修改配置文件mastersslavescore-site.xmlmapred-site.xmlhdfs-site.xmlhadoop-env.sh环境变量配置Hadoop2.0安装修改配置文件ha......
  • ES截取内嵌字段分组
    ES截取内嵌字段分组1背景根据ES的内嵌字段中的@符号截取第n个@符号之前的字符进行分组统计文档数量。该字段格式为:@xxx@yyy@zzz@、@aaa11@bbb222@ccc333@2映射{"ads_hmap_event_info":{"mappings":{"properties":{"CJSJ":{"type......
  • A4950/DRV8870/AT8870/AS4950
    从这里,我们就可以看到AS4950有4种驱动状态:1:IN1端口输入PWM,IN2端口输入低电平,芯片输出正电流,电机正转;2:IN1端口输入低电平,IN2端口输入PWM,芯片输出负电流,电机反转;3:IN1端口输入高电平,IN2端口输入PWM,芯片输出正电流,电机正传;4;IN1端口输入PWM,IN2端口输入高电平,芯片输出负电流,电机反转......
  • day45 1049.最后一块石头的重量II 494.目标和 474.一和零
    1049.最后一块石头的重量II本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。本题物品的重量为stones[i],物品的价值也为stones[i]。对应着01背包里的物品重量weight[i]和物品价值value[i]。思路:动规五部曲1.确定dp数组以及下......
  • 两颗i9-14900KS深度评测:探究不稳定的原因及解决办法
    一、前言:生来坎坷的i9-14900KS这是Intel最后一颗使用Intel7制程工艺的桌面处理器,可能也是多年来命途最为坎坷的顶级游戏处理器!我们早在3月份就收到了i9-14900KS,但因各种原因,直到今天才让大家见到这篇评测文章。i9-14900KS在规格上与i9-14900K相似,核心代号RaptorLake-SRefre......
  • 低代码开发系统是什么?它有那些部分组成?
    低代码开发系统是什么?它有那些部分组成?一、引言在当今快速变化的商业环境中,企业对于快速响应市场需求、降低开发成本和提高开发效率的需求日益增强。低代码开发系统(Low-CodeDevelopmentPlatform)应运而生,它通过减少手工编写代码的需求,提供了一种高效、快速且灵活的应用开发......