Premium Algo 100 - Hashing

Premium Algo 주제인 Hashing 이다.

---

Find Anagram Mappings
link : https://leetcode.com/problems/find-anagram-mappings/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
        vector<int> answer; 
        map<int,int> hashMap; 

        for(int i = 0; i < nums2.size(); i++){
            hashMap[nums2[i]] = i; 
        }

        for(int i = 0; i < nums1.size(); i++){
            answer.push_back(hashMap[nums1[i]]); 
        }

        return answer; 
    }
};

---

Palindrome Permutation
link : https://leetcode.com/problems/palindrome-permutation/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    bool canPermutePalindrome(string s) {
        map<char,int> hashMap; 
        for(char& c : s) hashMap[c]++; 

        int oddCount = 0; 
        for(auto& it : hashMap){
            oddCount += hashMap[it.first] % 2 ? 1  : 0; 
            if(oddCount > 1) return false; 
        }

        return true; 
    }
};

---

Sentence Similarity
link : https://leetcode.com/problems/sentence-similarity/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if(sentence1.size() != sentence2.size()) return false; 

        map<string,set<string>> hashMap; 
        int N = sentence1.size(); 

        for(vector<string>& v : similarPairs){
            hashMap[v[0]].insert(v[1]); 
            hashMap[v[1]].insert(v[0]); 
        }

        for(int i = 0; i < N; i++){
            string s1 = sentence1[i]; 
            string s2 = sentence2[i]; 

            bool flag = (hashMap[s1].contains(s2) || hashMap[s2].contains(s1) || s1 == s2); 

            if(!flag) return false;
        }

        return true; 

    }
};

---

Single-Row Keyboard
link : https://leetcode.com/problems/single-row-keyboard/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        map<char,int> hashMap; 
        int curr = 0, answer = 0; 
        for(int i = 0; i < keyboard.size(); i++) hashMap[keyboard[i]] = i; 
        for(char& c : word){
            answer += abs(hashMap[c] - curr); 
            curr = hashMap[c]; 
        }

        return answer; 
    }
};

---

Grpup Shifted Strings
link : https://leetcode.com/problems/group-shifted-strings/description/?envType=study-plan-v2&envId=premium-algo-100

`class Solution {
public:
    char shiftLetter(char letter, int shift){
        return (letter - shift + 26) % 26 + 'a'; 
    }

    string getHash(string& s){
        int shift = s[0]; 
        string hashKey;  

        for(char letter : s){
            hashKey += shiftLetter(letter, shift); 
        }

        return hashKey; 
    }
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> mapHashToList; 

        for(string str : strings){
            string hashKey = getHash(str); 
            mapHashToList[hashKey].push_back(str); 
        }

        vector<vector<string>> groups; 
        for(auto it : mapHashToList){
            groups.push_back(it.second); 
        }

        return groups; 
    }
}

---

Largest Unique Number
link : https://leetcode.com/problems/largest-unique-number/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int largestUniqueNumber(vector<int>& nums) {
        map<int,int> hashMap; 
        int answer = -1;

        for(int n : nums) hashMap[n]++;
        for(auto& it : hashMap){
            if(it.second == 1) answer = max(answer, it.first); 
        }

        return answer;
    }
};

---

Counting Elements
link : https://leetcode.com/problems/counting-elements/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int countElements(vector<int>& arr) {
        sort(arr.begin(), arr.end()); 
        map<int,int> hashMap; 
        int answer = 0; 
        for(int n : arr) hashMap[n]++; 

        for(int n : arr){
            if(hashMap.count(n+1)){
                answer++; 
            }
        }

        return answer; 
    }
};

---

Find Smallest Common Element in All Rows
link : https://leetcode.com/problems/find-smallest-common-element-in-all-rows/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        map<int,int> hashMap; 
        for(vector<int>& v : mat){
            for(int n : v) hashMap[n]++; 
        }

        int answer = INT_MAX; 

        for(auto& it : hashMap){
            if(it.second == mat.size()){
                answer = min(answer, it.first); 
            }
        }

        return answer == INT_MAX ? -1 : answer; 
    }
};

---

복습 필요한 문제

1. Group Shifted Strings : HashMap 개념을 조금 더 생각하고 풀었어야 하는 문제다. 다시 풀어봐도 좋을 느낌이다. String 개념도 같이 필요하다.

2. Find Smallest Common Element in All Rows : HashMap 으로 간단하게 풀 수 있었지만 다른 방법으로도 충분히 풀 수 있는 문제다. 다시 한번 도전해보자.