LeetCode刷题day23

​​49. 字母异位词分组​​

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]      

示例 3:

输入: strs = ["a"]
输出: [["a"]]      

思路分析

字母异位词其实就是两个串所使用的的字母以及个数都相同,只是顺序不同.所以如果两个串是字母异位词,则这两个串排序后是相同的.

• 我们可以使用map来存储解决,因为不要求有序和可重复性,所以我们可以使用 unordered_map
• 我们依次对字符串数组进行遍历,如果当前字符串排序后在map中出现过,则将其存入该key对应的val数组中.如果没有出现过则创建以该串为键的键值对.
• 最终将结果整理存放到vector数组中.

参考代码

vector<vector<string>> groupAnagrams(vector<string>& strs) {
  unordered_map<string,vector<string>> M;
  string temp;
  vector<vector<string>> res;
  for(string s : strs){
    temp = s;
    sort(s.begin(),s.end());
    if(M.find(s)==M.end()){
      vector<string> V;
      M[s] = V;
      M[s].push_back(temp);   
    }else{
      M[s].push_back(temp);
    }
  }
  unordered_map<string,vector<string>>::iterator it;
  for(it = M.begin();it!=M.end();it++){
    res.push_back(it->second);
  }
  return res;
}      

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]      

解释:

起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。

起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]      

解释:

起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。

起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。

起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

方法一:hash+暴力

参考代码1

vector<int> findAnagrams(string s, string p) {
  if(s.size()<p.size()) {
    return {};
  }
  vector<int> res;
  unordered_map<char,int> M;
  int n = p.size();
  for(char c : p) {
    if(M.find(c)==M.end()) {
      M[c] = 1;
    } else {
      M[c]++;
    }
  }

  for(int i = 0; i < s.size()-n; i++) {

    unordered_map<char,int> temp(M);
    for(int j = i; j<i+n; j++) {
      if(temp.find(s[j])==temp.end()) {
        break;
      } else {
        temp[s[j]]--;
        if(!temp[s[j]]) {
          temp.erase(s[j]);
        }
      }
    }
    if(!temp.size()) {
      res.push_back(i);
    }
  }
  return res;
}      

• 时间复杂度:

方法二:滑动窗口法+hash表.

• 先使用串p对arrP进行初始化.然后arrS用和p同样的长度进行初始化,这样两个窗口中的字符个数就相同了.
• 然后进行判断这两个数组是否相同,如果相同则是字母异位词.
• 如果不相同,s对应的窗口右移动继续判断…

参考代码2

vector<int> findAnagrams(string s, string p) {
  int m = s.size(),n = p.size();
  vector<int> res;
  if(m<n) {
    return {};
  }
  int arrS[26] = {0};
  int arrP[26] = {0};
  for(int i = 0; i < n; i++) {
    arrS[s[i]-'a']++;
    arrP[p[i]-'a']++;
  }
  if(judgeArray(arrS,arrP)) {
    res.push_back(0);
  }
  for(int i = n; i<m; i++) {
    arrS[s[i-n]-'a']--;//每次去除窗口的第一个字符 
    arrS[s[i]-'a']++;//将新的字符添加进去 
    if(judgeArray(arrS,arrP)) {
      res.push_back(i-n+1);// 如果满足题意则把窗口右边界添加进去. 
    }
  }
  return res;
}      

• 时间复杂度:
• 空间复杂度: