字母异位词（哈希映射法）

题目字母异位词是指两个字符串所含的字符种类与每种字符的数量完全相同仅字符的排列顺序不同。例如aabcbaaccbaa这三个字符串互为字母异位词。给定n个仅由小写英文字母组成的字符串请统计其中共有多少种不同的字母异位词类别即有多少组互为字母异位词的字符串集合。输入格式:第一行一个正整数n1≤n≤10000。接下来n行每行一个非空字符串每个字符串长度不超过1000且仅包含小写英文字母。输出格式:输出多行第一行为一个正整数表示不同的字母异位词类别的数量。接下来的多行每行输出一组字母异位词顺序和输入顺序一致两个字母异位词中间用一个空格分隔。输入样例:5abc bac def hik efd输出样例:3abc bacdef efdhik问题分析题目理解这道题的核心是识别字母异位词并分组输出。字母异位词的定义是字符种类和数量相同但排列顺序不同。例如abc、bac、cba是异位词都包含1个a、1个b、1个cabc和abd不是异位词字符种类不同算法思路本题采用的算法是哈希映射法核心思想是特征提取将每个字符串转化为它的特征向量即26个字母的计数数组哈希分组用特征向量作为key将所有相同特征的字符串放在一起顺序记录额外记录特征向量的出现顺序保证输出顺序符合要求代码详细分析#include bits/stdc.h using namespace std; // 数据结构定义 mapvectorint, vectorstring mp; // 哈希映射特征向量 - 该类的所有字符串 vectorvectorint v; // 记录特征向量的出现顺序 // 计算字符串的特征向量哈希值 vectorint get_hash(string s) { int ans[27]; // 计数数组实际只用0-25 // 初始化计数数组为0 for (int i 0; i 26; i) { ans[i] 0; } // 统计每个字母出现的次数 for (auto i : s) { ans[i - a]; // a对应下标0b对应1以此类推 } // 将计数数组转换为vector vectorint vec; for (int i 0; i 26; i) { vec.push_back(ans[i]); } return vec; } int main() { int n; cin n; // 处理每个输入的字符串 for (int i 1; i n; i) { string s; cin s; // 计算当前字符串的特征向量 vectorint tmp get_hash(s); // 如果是新的特征向量新的异位词类别记录它的出现顺序 if (!mp.count(tmp)) { v.push_back(tmp); } // 将当前字符串加入对应的类别 mp[tmp].push_back(s); } // 输出异位词类别的数量 cout mp.size() \n; // 按输入顺序输出每个类别 for (int i 0; i v.size(); i) { int size mp[v[i]].size(); // 当前类别的字符串数量 // 输出该类别的所有字符串 for (int j 0; j size; j) { cout mp[v[i]][j]; if (j ! size - 1) cout ; // 最后一个不加空格 } // 最后一行不加换行 if (i ! v.size() - 1) cout \n; } return 0; }算法核心特征向量的设计为什么用26个字母的计数数组作为特征因为两个字符串是字母异位词当且仅当它们的字母计数数组完全相同。例如abc→ [1,1,1,0,0,...]a出现1次b出现1次c出现1次其他0bac→ [1,1,1,0,0,...]完全相同aabc→ [2,1,1,0,0,...]不同a出现2次数据结构的巧妙运用1.mapvectorint, vectorstring mpKey:vectorint类型的特征向量Value:vectorstring存储该类的所有字符串为什么用map而不是unordered_mapvectorint可以作为map的key需要比较大小unordered_map需要为vectorint提供哈希函数这里简化处理2.vectorvectorint v记录特征向量出现的顺序因为map的遍历顺序是按照key排序的不是输入顺序用v保存顺序保证输出时按输入顺序算法流程示例以输入样例为例5 abc bac def hik efd处理过程abc→ 特征向量 [1,1,1,0,...] → mp中新增该类v记录该特征bac→ 同特征 [1,1,1,0,...] → 加入已有类别def→ 特征 [0,0,0,1,1,1,0,...] → 新增类别v记录hik→ 特征 [0,0,0,0,0,0,0,1,1,0,1,0,...] → 新增类别v记录efd→ 同def的特征 → 加入已有类别最终数据结构mp: [1,1,1,0,...] → [abc, bac] [0,0,0,1,1,1,0,...] → [def, efd] [0,0,0,0,0,0,0,1,1,0,1,0,...] → [hik] v: [[1,1,1,0,...], [0,0,0,1,1,1,0,...], [0,0,0,0,0,0,0,1,1,0,1,0,...]]输出3 abc bac def efd hik时间复杂度分析特征向量计算O(L)L为字符串长度本题L≤1000总计算O(n × L) ≤ 10000 × 1000 10^7可接受map操作O(log m)m为类别数可忽略空间复杂度分析存储所有字符串O(总字符数)特征向量每个类别26个int最多n个类别总结本题的算法精髓是特征提取用字母计数数组唯一标识异位词类别哈希分组用map将相同特征的字符串聚在一起顺序记录用额外的vector保持输入顺序AC代码#include bits/stdc.h using namespace std; //记录字符串顺序 mapvectorint, vectorstring mp; //记录异位词顺序 vectorvectorint v; //计算哈希值 vectorint get_hash(string s) { int ans[27]; for (int i 0; i 26; i) { ans[i] 0; } for (auto i : s) { ans[i - a]; } vectorint vec; for (int i 0; i 26; i) { vec.push_back(ans[i]); } return vec; } int main() { int n; cin n; for (int i 1; i n; i) { string s; cin s; //去重 vectorint tmp get_hash(s); if (!mp.count(tmp)) { v.push_back(tmp); } mp[tmp].push_back(s); } cout mp.size() \n; for (int i 0; i v.size(); i) { int size mp[v[i]].size(); for (int j 0; j size; j) { cout mp[v[i]][j]; if (j ! size - 1) cout ; } if (i ! v.size() - 1) cout \n; } return 0; }