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

9. Palindrome Number

https://leetcode.com/problems/palindrome-number/description/
Solution 1. Only compare half digits (fastest). Corner cases are (x!=0 && x%10 == 0).
    bool isPalindrome(int x) {
        if(x<0 || (x!=0 && x%10==0)) return false;
        int y = 0;
        while(x>y) {
            y = y*10 + (x%10);
            x /= 10;
        }
        return x == y || (x == y/10);
    }
Solution 1.1 Reverse whole number
    bool isPalindrome(int x) {
        if(x<0) return false;
        int a = x;
        int y = 0;
        while(a) {
            y = y*10 + (a%10);
            a /= 10;
        }
        return x == y;
    }
Solution 2. Covert to string and compare it to its reverse.
    bool isPalindrome(int x) {
        if(x<0) return false;
        string s = to_string(x);
        string t = s;
        reverse(begin(t),end(t));
        return s == t;
    }
Solution 2.1 Two pointers for string.
    bool isPalindrome(int x) {
        if(x<0) return false;
        string s = to_string(x);
        for(int i=0, j=s.size()-1;i<j; i++,j--){
            if(s[i] != s[j]) return false;
        }
        return true;
    }

459. Repeated Substring Pattern

https://leetcode.com/problems/repeated-substring-pattern/description/
Solution 0. Use KMP algorithm. 
Construct the longest proper prefix which is also suffix: lps[] with size M = s.size().
the length of the last longest proper prefix is lps[M-1]. The string repeating of sub string only when:
1. lps[M-1] != 0, and
2. lps[M-1]%(M-lps[M-1]) == 0, and the non-repeating substr is s[0 ... M-lps[M-1]-1].
    bool repeatedSubstringPattern(string s) {
        int len = 0, i = 1, M = s.size();
        vector<int> lps(M, 0);
        while(i<M) {
            if(s[len] == s[i]) lps[i++] = ++len;
            else {
                if(len != 0) len = lps[len-1];
                else lps[i++] = 0;
            }
        }
        return lps[M-1] && lps[M-1]%(M-lps[M-1]) == 0;
    }
Solution 1. Shift T chars to the end of string and compare.

    bool repeatedSubstringPattern(string str) {

        string shiftedStr;

        int N = str.size();

        for(int T=1; T <= N/2; T++) {

            if(N%T == 0) {

                shiftedStr = shiftStr(str, T);

                if(str == shiftedStr) return true;

            }

        }

        return false;

    }

    string shiftStr(string& str, int T) {

        string ret = str.substr(T);

        ret += str.substr(0,T);

        return ret;

    }

Solution 2. A naive solution. Assume there are K parts of substr for s, and the size for each part is T. Check T chars K times to see if they are equal.
    bool repeatedSubstringPattern(string s) {
        int N = s.size();
        for(int T=1; T<=N/2; T++) {
            if(N%T != 0) continue;
            int K = N/T;
            int k;
            for(k=1; k<K; k++) {
                if(s.substr(0, T) != s.substr(k*T, T)) break;
            }
            if(k==K) return true;
        }
        return false;
    }

345. Reverse Vowels of a String

https://leetcode.com/problems/reverse-vowels-of-a-string/description/
Solution 1. Use array as a map.
    string reverseVowels(string s) {
        vector<int> mp('z'+1, 0);
        mp['a'] = 1, mp['A'] = 1;
        mp['e'] = 1, mp['E'] = 1;
        mp['i'] = 1, mp['I'] = 1;
        mp['o'] = 1, mp['O'] = 1;
        mp['u'] = 1, mp['U'] = 1;
        for(int i=0, j=s.size()-1; i<j;) {
            if(mp[s[i]] && mp[s[j]]) {
                swap(s[i], s[j]);
                i++;
                j--;
                continue;
            }
            if(!mp[s[i]]) i++;
            if(!mp[s[j]]) j--;
        }
        return s;
    }
Solution 2. Use a map.
    string reverseVowels(string s) {
        unordered_map<char, int> mp = {{'a', 1}, {'e',1}, {'i',1},{'o',1},{'u',1}
                                      ,{'A', 1}, {'E',1}, {'I',1},{'O',1},{'U',1}};
        for(int i=0, j=s.size()-1; i<j;) {
            if(mp.count(s[i]) && mp.count(s[j])) {
                swap(s[i], s[j]);
                i++;
                j--;
            }
            if(!mp.count(s[i])) i++;
            if(!mp.count(s[j])) j--;
        }
        return s;
    }

645. Set Mismatch

https://leetcode.com/problems/set-mismatch/description/
Solution 0. Use XOR and count numbers
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> cnt(nums.size(),0);
        vector<int> res = {0, 0};
        for(int i=0; i<nums.size(); i++) {
            if(++cnt[nums[i]-1] == 2)
                res[0] = nums[i];
            res[1] ^= (i+1)^nums[i];
        }
        res[1] ^= res[0];
        return res;
    }
Solution 1.  Sort by putting nums[i] at index nums[i]-1
   vector<int> findErrorNums(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++) {
            while(nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
        }
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] != i+1) return {nums[i], i+1};
        }
    }

Solution 2. Use bitset
    vector<int> findErrorNums(vector<int>& nums) {
        bitset<10000> bits(0);
        vector<int> res;
        for(auto n: nums) {
            if(bits.test(n-1)) res.push_back(n);
            else bits.set(n-1);
        }
        for(int i=0; i<bits.size(); i++) {
            if(!bits[i]) {
                res.push_back(i+1);
                break;
            }
        }
        return res;
    }

572. Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/description/
Solution 1. Compare s to t, if they are not identical, then compare subtrees of s to t.
    bool isIdentical(TreeNode*s, TreeNode* t) {
        if(!s && !t) return true;
        if(!s || !t) return false;
        if(s->val != t->val) return false;
        return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        if(isIdentical(s, t)) return true;
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
Solution 1.1. Only compare t to the subtrees of s that have same depth as t.
class Solution {
    vector<TreeNode*> vd;
public:
    int getDepth(TreeNode* s, int d){
        if(!s) return 0;
        int depth = 1 + max(getDepth(s->left, d), getDepth(s->right, d));
        if(depth == d) {
            vd.push_back(s);
        }
        return depth;
    }
    bool isIdentical(TreeNode*s, TreeNode* t) {
        if(!s && !t) return true;
        if(!s || !t || s->val != t->val) return false;
        return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        getDepth(s, getDepth(t, -1));
        for(TreeNode* n: vd){
            if(isIdentical(n, t)) return true;
        }
        return false;
    }

};
Solution 2. Convert tree to string and compare
    void traversal(TreeNode* node, vector<string>& s) {
        if(!node) {
            s.push_back("#"); return;
        }
        s.push_back(to_string(node->val));
        traversal(node->left, s);
        traversal(node->right, s);
    }
    bool isSub(vector<string>& s, vector<string>& t) {
        if(s.size()<t.size()) return false;
        for(int i=0; i<s.size();i++){
            if(s[i]!=t[0]) continue;
            for(int ii=i, j=0; ii<s.size() && j<t.size(); ii++, j++) {
                if(s[ii]!=t[j]) break;
                if(j==t.size()-1) return true;
            }
        }
        return false;
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        vector<string> ss, ts;
        traversal(s, ss);
        traversal(t, ts);
        return isSub(ss, ts);
    }

242. Valid Anagram

https://leetcode.com/problems/valid-anagram/description/
Solution 1. Use array as map.
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size()) return false;
        int cnt[26] = {0};
        for(int i=0; i<s.size();i++){
           // do the counting in one loop
            cnt[s[i]-'a']++;
            cnt[t[i]-'a']--;
        }
        for(int i=0;i<26;i++){
            if(cnt[i] != 0) return false;
        }
        return true;
    }
Solution 2. Compare sorted string.
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return(s==t);
    }

455. Assign Cookies

https://leetcode.com/problems/assign-cookies/description/
Solution 1. sort and match
 int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int res = 0;
        for(int i=0,j=0;i<g.size()&&j<s.size();) {
            if(g[i]<=s[j]) {
                i++;j++;res++;
            }
            else
               j++;
        }
        return res;
    }