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;
}      

• 時間複雜度:
• 空間複雜度: