748. Shortest Completing Word

    string shortestCompletingWord(string lp, vector<string>& words) {
        transform(lp.begin(), lp.end(), lp.begin(), ::tolower);
        string res;
        int sz = 16;
        unordered_map<char,int> lm;
        for(char c: lp) {
            if(c>='a' && c<='z') lm[c]++;
        }
        for(auto &s: words) {
            if(s.size()<sz) {
                unordered_map<char,int> tm = lm;
                for(char c : s) if(tm.count(c)) tm[c]--;
                bool complete = true;
                for(auto &m: tm) {
                    if(m.second>0) {complete = false; break;}
                }
                if(complete) {
                    res = s;
                    sz = s.size();
                }
            }
        }
        return res;
    }

743. Network Delay Time

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int dmax = 1e7;
        vector<bool> used(N+1, false);
        vector<int> d(N+1, dmax);
        vector<vector<pair<int,int>>> u2v(N+1);
        for(int i=0; i<times.size(); i++) {
            u2v[times[i][0]].push_back({times[i][1], times[i][2]});
        }
        queue<int> q;
        q.push(K);
        d[K] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
// make current node available because signal delay may be smaller through a different path that has not been counted
            used[u] = false;
            for(auto &p: u2v[u]){
                int v = p.first, w = p.second;
                int dv = d[u] + w;
                if(dv < d[v]) {
                    d[v] = dv;
                    if(!used[v]) {
                        q.push(v);
                        used[v] = true;
                    }
                }
            }   
        }
        int res = 0;
        for(int i=1; i<N+1; i++) {
            if(d[i]>=dmax) return -1;
            res = max(res, d[i]);
        }
        return res;
    }

721. Accounts Merge

https://leetcode.com/problems/accounts-merge/description/
    vector<vector<string>> accountsMerge(vector<vector<string>>& a) {
        int N = a.size();
        if(N<=1) return a;
        vector<int> person(N);
        for(int i=0; i<N; i++) person[i] = i;
        unordered_map<string, int> m1;
        for(int i=0; i<N; i++) {
            vector<string> vs = a[i];
            for(int j=1; j<vs.size(); j++) {
                if(m1.count(vs[j])) {
                    int k = m1[vs[j]];
                    while(k != person[k]) k = person[k];
                    person[k] = i;
                }
                m1[vs[j]] = i;
            }
        }
        unordered_map<int, set<string>> m2;
        vector<int> id(N, -1);
        for(int i=0; i<N; i++) {
            int k = person[i];
            while(k!=person[k]) k=person[k];
            for(int j=1; j<a[i].size(); j++) m2[k].insert(a[i][j]);
        }
        vector<vector<string>> res;
        for(auto& m : m2) {
            vector<string> vs;
            vs.push_back(a[m.first][0]);
            for(auto& s: m.second) {
                vs.push_back(s);
            }
            res.push_back(vs);
        }
        return res;
    }

Customized hash function

You need to provide a suitable hash function for your key type. A simple example:
https://stackoverflow.com/questions/32685540/c-unordered-map-with-pair-as-key-not-compiling

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

423. Reconstruct Original Digits from English

https://leetcode.com/problems/reconstruct-original-digits-from-english/description/
Solution 1. no need to sort. (19 ms)
    string originalDigits(string s) {
        string res;
        vector<string> ns = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        // order to check the numbers
        vector<int> order = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
        // distinct char of each number
        vector<char> orderc = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
        vector<int> m(256,0);
        vector<string> part(10,"");
        for(char& c: s) m[c]++;
        for(int i=0; i<10; i++) {
            int n = order[i];
            char key = orderc[i];
            int cnt = m[key];  // count to be remove for each char in a word
            for(char& c : ns[n]) m[c] -= cnt;
            part[n] = string(cnt, char('0' + n));

        }
        for(string& p : part) res += p;
        return res;
    }
or,
    string originalDigits(string s) {
        string res;
        vector<string> ns = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        vector<int> order = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
        vector<char> orderc = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
        vector<int> m(256,0);
        for(char& c: s) m[c]++;
        for(int i=0; i<10; i++) {
            int n = order[i];
            char key = orderc[i];
            while(m[key] > 0) {
                for(char& c : ns[n]) m[c]--;
                res += to_string(n);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }

12. Integer to Roman

https://leetcode.com/problems/integer-to-roman/description/
    string intToRoman(int num) {
        map<int, string, greater<int>> I2R = {
            {1000, "M"}, {500, "D"}, {100, "C"}, {50, "L"}, {10, "X"}, {5, "V"}, {1, "I"},
            {900, "CM"}, {400, "CD"}, {90, "XC"}, {40, "XL"}, {9, "IX"}, {4, "IV"}
        };
        string res;
        for(auto const& r : I2R) {
            int c = num/r.first;
            if(c==1) { res += r.second; num -= r.first;}
            else if(c>1) { res += string(c, r.second[0]); num -= c*r.first;}
        }
        return res;
    }
or,
    string intToRoman(int num) {
        string res;
        vector<string> M = {"", "M", "MM", "MMM"};
        vector<string> C = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        vector<string> X = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        vector<string> I = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    }

554. Brick Wall

https://leetcode.com/problems/brick-wall/description/
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int,int> mp;
        for(auto & v : wall) {
            int w = 0;
            for(int i=0; i<v.size()-1; i++) {
                w += v[i];
                mp[w]++;
            }
        }
        int NW = wall.size(), res = NW;
        for(auto &m: mp) {
            int n = NW - m.second;
            if(n<res) res = n;
        }
        return res;
    }

697. Degree of an Array

    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int,int> f;
        unordered_map<int,int> start;
        unordered_map<int,int> end;
        int mx = 0;
        for(int i=0; i<nums.size(); i++) {
            int n = nums[i];
            f[n]++;
            if(!start.count(n)) start[n] = i;
            end[n] = i;
            if(f[n]>mx) mx = f[n];
        }
        int res = nums.size();
        for(auto &m: f) {
            if(m.second == mx) {
                int len = end[m.first] - start[m.first] + 1;
                if(len<res) res = len;
            }
        }
        return res;
    }

454. 4Sum II

https://leetcode.com/problems/4sum-ii/description/
Solution 1. Save a loop for solution 2.
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> m1, m2;
        for(auto &a : A)
            for(auto &b : B) {
                m1[a+b]++;
            }
        int res = 0;
        for(auto &c : C)
            for(auto &d : D) {
                if(m1.count(-(c+d))) res += m1[-(c+d)];
            }
        return res;
    }
Solution 2.
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> m1, m2;
        for(auto &a : A)
            for(auto &b : B) {
                m1[a+b]++;
            }
        for(auto &c : C)
            for(auto &d : D) {
                m2[-(c+d)]++;
            }
        int res = 0;
        for(auto &m : m1) {
            if(m2.count(m.first)) res += m.second * m2[m.first];
        }
        return res;
    }

648. Replace Words

https://leetcode.com/problems/replace-words/description/
Solution 1. Trie search
class Solution {
#define NAL 26
    struct trieNode {
        trieNode* child[NAL] = {nullptr};
        bool isEnd = false;
    };
    void insert(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->child[key[i]-'a'] == nullptr) {
                p->child[key[i]-'a'] = new trieNode;
            }
            p = p->child[key[i]-'a'];
            if(p->isEnd == true) return;
        }
        p->isEnd = true;
    }
    int search(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->isEnd == true){ return i; }
            if(p->child[key[i]-'a'] == nullptr) return 0;
            p = p->child[key[i]-'a'];
        }
        return 0;
    }
public:
    string replaceWords(vector<string>& dict, string sentence) {
        trieNode* root = new trieNode;
        for(string &s : dict) {
            insert(root, s);
        }
        string res = "", word;
        istringstream iss(sentence);
        while(iss>>word) {
            cout<<endl;
            int len = search(root, word);
            if(len) res += " " + word.substr(0,len);
            else res += " " + word;
        }
        return res.substr(1);
    }
};

347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        vector<int> res;
        vector<pair<int,int>> v;
        for(int n: nums) mp[n]++;
        for(auto &m: mp) v.push_back({m.first,m.second});
        sort(v.begin(),v.end(), [&](pair<int,int>&a, pair<int,int>&b){return a.second>b.second;});
        for(int i=0; i<k; i++) res.push_back(v[i].first);
        return res;
    }
Solution 2. Use priority_queue
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(int n: nums) mp[n]++;
        priority_queue<pair<int,int>> q;
        for(auto &m : mp) q.push({m.second, m.first});
        vector<int> res;
        for(int i=0; i<k; i++) {
            res.push_back(q.top().second);
            q.pop();
        }
        return res;
    }
or,
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(int n: nums) mp[n]++;
        map<int,vector<int>> buck;
        for(auto &m : mp) {
            buck[m.second].push_back(m.first);
        }
        vector<int> res;
        for(map<int,vector<int>>::reverse_iterator it=buck.rbegin(); it!=buck.rend(); it++) {
            for(auto& n: it->second) {
                res.push_back(n);
                if(res.size()==k) return res;
            }
        }
        return res;
    }

676. Implement Magic Dictionary

https://leetcode.com/problems/implement-magic-dictionary/description/
class MagicDictionary {
    unordered_map<string,vector<pair<int,char>>> d;
public:
    /** Initialize your data structure here. */
    MagicDictionary() {
     
    }
 
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for(string s : dict) {
            for(int i=0; i<s.size(); i++) {
                string w = s.substr(0, i) + s.substr(i+1);
                d[w].push_back({i, s[i]});
            }
         
        }
    }
 
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        for(int i=0; i<word.size(); i++) {
            string w = word.substr(0, i) + word.substr(i+1);
            if(d.count(w)) {
                for(auto& p : d[w]) {
                    if(p.first == i && p.second != word[i]) return true;
                }
            }
        }
        return false;
    }
};

609. Find Duplicate File in System

https://leetcode.com/problems/find-duplicate-file-in-system/description/
    vector<vector<string>> findDuplicate(vector<string>& paths) {
        unordered_map<string,vector<string>> con2path;
        for(string pth : paths) {
            stringstream ss(pth);
            string item;
            getline(ss, item, ' ');
            string path = item + "/";
            while(getline(ss, item, ' ')) {
                //size_t l = item.find('(');
                //size_t r = item.find(')');
                //string fname = path + item.substr(0, l);
                //string content = item.substr(l+1, r-l);
                stringstream ssi(item);
                string fname;
                getline(ssi, fname, '(');
                fname = path + fname;
                string content;
                getline(ssi, content, ')');
                con2path[content].push_back(fname);
            }
        }
        vector<vector<string>> res;
        for(auto &x : con2path) if(x.second.size()>1) res.push_back(x.second);
        return res;
    }

535. Encode and Decode TinyURL

https://leetcode.com/problems/encode-and-decode-tinyurl/description/
class Solution {
    unordered_map<string, string> encodeMap;
    unordered_map<string, string> decodeMap;
    string dict = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if(encodeMap.count(longUrl)) return encodeMap[longUrl];
        string shortUrl = "http://tinyurl.com/";
        int n = encodeMap.size(), nd = dict.size();
        while(n) {
            shortUrl += dict[n%nd];
            n /= nd;
        }
        encodeMap[longUrl] = shortUrl;
        decodeMap[shortUrl] = longUrl;
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return decodeMap[shortUrl];
    }
};

532. K-diff Pairs in an Array

https://leetcode.com/problems/k-diff-pairs-in-an-array/description/
    int findPairs(vector<int>& nums, int k) {
        if(k<0) return 0;
        unordered_map<int,int> mp;
        int res = 0;
        for(auto n: nums) mp[n]++;
        if(k==0) {
            for(auto &x : mp) {
                res += (x.second>1);
            }
            return res;
        }
        for(auto &x : mp) {
            if(mp.count(x.first+k)) res++;
        }
        return res;
    }

677. Map Sum Pairs

https://leetcode.com/problems/map-sum-pairs/description/

Implement a MapSum class with insert, and sum methods.

For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

class MapSum {
    unordered_map<string,int> mp;
public:
    /** Initialize your data structure here. */
    MapSum() {
    }
    void insert(string key, int val) {
        mp[key] = val;
    }
    int sum(string prefix) {
        int s = 0;
        for(auto & x: mp) {
            if(x.first.size()>=prefix.size()) {
                int i;
                for(i=0; i<prefix.size(); i++) {
                    if(x.first[i]!=prefix[i]) break;
                }
                if(i==prefix.size()) s += x.second;
            }
        }
        return s;
    }
};

219. Contains Duplicate II

https://leetcode.com/problems/contains-duplicate-ii/description/
Solution 1. Use map to store the index for each distinct number.
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size()<2) return false;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); i++) {
            if(mp.count(nums[i]))
                if(i - mp[nums[i]]<=k) return true;
            mp[nums[i]] = i;
        }
        return false;
    }
Solution 2. Use unordered_set to maintain a set containing nums[i-k,...,i-1].
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size()<2 || k<=0) return false;
        unordered_set<int> st;
        for(int i=0; i<nums.size(); i++) {
            if(st.count(nums[i]))
                return true;
            else {
                if(i-k>=0) st.erase(nums[i-k]);
                st.insert(nums[i]);
            }
        }
        return false;
    }

290. Word Pattern

https://leetcode.com/problems/word-pattern/description/
Solution 1.0 Read the string one by one and compare. Use stringstream the read. (0 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        string item;
        int i=0, n=pattern.size();
        for(; getline(ss, item, ' ');i++) {
            if(i==n || mp[pattern[i]] != ms[item]) return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;

    }
Solution 1.2 Use istringstream
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        istringstream in(str);
        int i = 0, n = pattern.size();
        for(string item; in>>item;i++) {
            if(i==n || mp[pattern[i]]!=ms[item])
                return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;
    }
Solution 1.1 Convert the string to a vector<string> and compare. (3 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        vector<string> s;
        string item;
        while(getline(ss, item, ' ')) {
            s.push_back(item);
        }
        if(pattern.size() != s.size()) return false;
        for(int i=0; i<s.size();i++) {
            if(!mp.count(pattern[i]) && !ms.count(s[i])) {
                mp[pattern[i]] = i+1;
                ms[s[i]] = i+1;
            }
            if(!mp.count(pattern[i]) || !ms.count(s[i])) return false;
            if(mp[pattern[i]] != ms[s[i]]) return false;
        }
        return true;
    }

438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size()) return {};
        int np = p.size();
        vector<int> stat('z'+1, 0), res;
        for(int i=0; i<np; i++) {
            stat[s[i]]++;
            stat[p[i]]--;
        }
        stat[s[np-1]]--;
        for(int i=np-1; i<s.size(); i++) {
            stat[s[i]]++;
            int j = 0;
            for(j='a'; j<'z'+1; j++) {
                if(stat[j]!=0) break;
            }
            if(j=='z'+1) res.push_back(i-np+1);
            stat[s[i-np+1]]--;
        }
        return res;
    }

205. Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/description/
Solution 0. Store the same index for the last appearance of s[i] and t[i] to two arrays. If the indices for s[i] and t[i] are different, they are not isomorphic.
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        int mps[256] = {0}, mpt[256] = {0};
        for(int i=0; i<s.size(); i++) {
            if(mps[s[i]] != mpt[t[i]])
                return false;
            mps[s[i]] = i+1;
            mpt[t[i]] = i+1;
        }
        return true;
    }
Solution 1. Use array as map
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        //vector<char> mps(256, 0), mpt(256, 0);
        char mps[256] = {0};
        char mpt[256] = {0};
        for(int i=0; i<s.size(); i++) {
            if(!mps[s[i]] && !mpt[t[i]]) {
                mps[s[i]] = t[i];
                mpt[t[i]] = s[i];
            }
            else if(mps[s[i]] != t[i] || mpt[t[i]] != s[i])
                return false;
        }
        return true;
    }
Solution 1.1 use map
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        unordered_map<char,char> mp, mq;
        for(int i=0; i<s.size(); i++) {
            if(!mp.count(s[i]) && !mq.count(t[i])) {
                mp[s[i]] = t[i];
                mq[t[i]] = s[i];
            }
            else if(mp[s[i]] != t[i] || mq[t[i]] != s[i]) return false;
        }
        return true;
    }