文章目录

    • leetcode242.有效的字母异位词
      • 基本思路
      • AC-code
    • leetcode383. 赎金信
      • 基本思路
      • AC-code
    • leetcode49.字母异位词分组
      • 基本思路
      • AC-code
    • leetcode438.找到字符串中所有字母异位词
      • 基本思路
      • AC-code

leetcode242.有效的字母异位词

链接

基本思路

思路实际上很简单，可以使用数组进行构建字典，也可以使用map进行构建字典，区别实际上不大，下面是采用map进行构建的例子。

AC-code

class Solution {public:bool isAnagram(string s, string t) {//定义俩个哈希函数unordered_map<char,int>maps;unordered_map<char,int>mapt;//统计s的字母以及其字母出现的次数for(auto i : s)maps[i]++;//统计t的字母以其字母出现的次数for(auto i : t)mapt[i]++;//进入判断是否元素都相同，并且size大小一样。if(maps == mapt)return true;elsereturn false;}};

相同的由于数据量比较小 只有0-25，实际上为了提升速度，实际上使用的是数组进行书写，对应的AC-code如下：

class Solution {public:bool isAnagram(string s, string t) {int record[26] = {0};for (int i = 0; i < s.size(); i++) {// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了record[s[i] - 'a']++;}for (int i = 0; i < t.size(); i++) {record[t[i] - 'a']--;}for (int i = 0; i < 26; i++) {if (record[i] != 0) {// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。return false;}}// record数组所有元素都为零0，说明字符串s和t是字母异位词return true;}};

leetcode383. 赎金信

链接

基本思路

实际上思路是跟随着上一题一样，就是先创建两个哈希表用于储存对应的索引，然后判断前者的元素是否在后者元素当中，并且是否全部都出现且大于，如果是的就判断成功。

AC-code

class Solution {public:bool canConstruct(string ransomNote, string magazine) {//先定义两个哈希数组unordered_map<char,int>map_Note;unordered_map<char,int>map_Magazine;//统计俩个字符串中的字符for(auto i : ransomNote)++map_Note[i];for(auto i : magazine)++map_Magazine[i];//进行判断是否可以满足，条件ransomNote当中的元素都可以在magazine当中找到，并且在magazine当中的数目都要比ransomeNote来得多for(auto p : map_Note){if(map_Magazine.find(p.first) != map_Magazine.end() && map_Magazine[p.first] >= p.second){continue;}else{return false;}}return true;}};

与上面相同的是，实际上也是由于数据量比较小，所以使用数组作为哈希表即可，对应的哈希表是：

class Solution {public:bool canConstruct(string ransomNote, string magazine) {int record[26] = {0};//addif (ransomNote.size() > magazine.size()) {return false;}for (int i = 0; i < magazine.length(); i++) {// 通过recode数据记录 magazine里各个字符出现次数record[magazine[i]-'a'] ++;}for (int j = 0; j < ransomNote.length(); j++) {// 遍历ransomNote，在record里对应的字符个数做--操作record[ransomNote[j]-'a']--;// 如果小于零说明ransomNote里出现的字符，magazine没有if(record[ransomNote[j]-'a'] < 0) {return false;}}return true;}};

leetcode49.字母异位词分组

链接

基本思路

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

先分析一下题目，此种类型为分类输出的，自然而然就想到需要使用哈希表，但是对于哈希表的key-value的定义就还需要进行斟酌，这边写出个人关于此题的理解，后面补充官方题解。

第一步确认key，自然需要的是类别，实际上就是让相同的字母异位词进行对应，对于相同的锁定相同的key，然后value就输出的是所出现过的字母异位词。而关于这一步个人有两种写法：写法1使用双重map进行索引，第2种就是自行编一个哈希函数，进行确定索引，故有下面的方法。

实现
遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

AC-code

class Solution {public:vector<vector<string>> groupAnagrams(vector<string>& strs) {//确定一个哈希表用于储存字母异位词-结果unordered_map<string,vector<string>>map_strs;//储存答案的vectorvector<vector<string>>result;//统计并且归类for(auto i : strs){//挑选存储的key值//个人易错点：容易写成这样子。。。string temp = sort(i.begin(),i.end());string temp = i;sort(temp.begin(),temp.end());//由于使用sort函数，实际上本质就是应用了一层哈希函数，进行对齐，此时直接进行储存即可。map_strs[temp].push_back(i);}//输出答案for(auto& [key,value] : map_strs)result.push_back(value);return result;}};

leetcode438.找到字符串中所有字母异位词

链接

基本思路

实际上的思路就是哈希数组与滑动窗口的结合思想，做法还是很简单的，见下即可，值得关注的是，对于容器来说，我们想要比较内部元素是否都相等，可以直接进行==比较，而不用使用for循环进行对比，这是和数组不一样的地方，值得关注

AC-code

class Solution {public:vector<int> findAnagrams(string s, string p) {//滑动窗口，以及定义一个哈希数组int begin = 0, end = 0;vector<int>mapp(26,0);vector<int>maps(26,0);//分别取出s和p的长度int lens = s.size();int lenp = p.size();//创建一个返回最后结果的vectorvector<int>result;//开始统计p当中的字符串for(auto i : p)mapp[i - 'a']++;//开始滑动窗口进行统计s，并且当对应的长度一致的时候进行对比两个哈希数组是否相同，相同的话就是返回，不相同就继续滑动窗口。for(end = 0; end != lens ; end++){//先导入字符maps[s[end] - 'a']++;//再判断字符数量是否已经相同了if(end - begin == lenp - 1){//相同了实际上就可以进行判断两个map数组是否是一样的，如果是一样的，就塞入返回数组中，不满足就正常执行（移动begin，删除begin对应的字符数量）if(mapp == maps)result.push_back(begin);//删除begin元素，并将begin元素移动+1maps[s[begin] - 'a']--;begin++;}}return result;}};