409. Longest Palindrome

Very straightforward solution. Count the frequency for characters in the input string. If a character appears even times, it must be a part of palindrome. On the other hand, if a character appears odd times, then we want to add (odd times - 1). In the end, if there is odd time character, the return value should be added one.

1:  class Solution {  
2:  public:  
3:    int longestPalindrome(string s) {  
4:      unordered_map<char, int> mp;  
5:      for (c : s) mp[c]++;  
6:      int res = 0, odd = 0;  
7:      for (auto it : mp) {  
8:        if (it.second & 1) { res += it.second - 1, odd = 1; }  
9:        else res += it.second;  
10:      }  
11:      return res + odd;  
12:    }  
13:  };  

267. Palindrome Permutation I

The trick here as the hint says is we only need to track the first half string. So we need to count the number for the first half string. Also, we need to keep the middle character if the string has an odd length. And finally, we need to use hashtable to store each character’s count. After that, the problem becomes a classic backtracking permutation problem.

I used vector as hash table in first place. But I got TLE. I guess it’s too cost to check for 256 characters every time. Also when doing unordered_map, the iterator it in the loop “for (auto it : mp)” is a copy not the real iterator itself. So if you update this copy, it doesn’t change the content of the unordered_map at all. So we need to do either “for (auto &it : mp)” or “for (auto it=mp.begin(); it != mp.end(); i++)”.

1:  class Solution {  
2:  public:  
3:    vector<string> generatePalindromes(string s) {  
4:      unordered_map<char, int> mp;  
5:      vector<string> res;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        mp[s[i]]++;  
8:      }  
9:      int odd = 0, len = 0;  
10:      string mid = "";  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        if (it->second & 1) { odd++; mid += it->first; }  
13:        it->second /= 2;  
14:        len += it->second;  
15:      }  
16:      if (odd > 1) return res;  
17:      gen(mp, len, mid, "", res);  
18:      return res;  
19:    }  
20:    void gen(unordered_map<char, int> &mp, int len, string &mid, string s, vector<string> &res) {  
21:      if (s.size() == len) {  
22:        string r = s;  
23:        reverse(r.begin(), r.end());  
24:        res.push_back(s+mid+r);  
25:        return;  
26:      }  
27:      for (auto it = mp.begin(); it != mp.end(); it++) {  
28:        if (it->second > 0) {  
29:          it->second--;  
30:          gen(mp, len, mid, s+it->first, res);  
31:          it->second++;  
32:        }  
33:      }  
34:    }  
35:  };  

244. Shortest Word Distance II

My first impression is the hash table. The key value pair is (word, index). Since there could be duplicate words, the index should be a vector. Then the problem becomes to find shortest distance in two sorted vector. We can have two pointers. Everytime, we move the pointer who points to a smaller index.

1:  class WordDistance {  
2:  private:  
3:    unordered_map<string, vector<int>> mp;   
4:  public:  
5:    WordDistance(vector<string>& words) {  
6:      for (int i = 0; i < words.size(); i++) {  
7:        mp[words[i]].push_back(i);  
8:      }  
9:    }  
10:    int shortest(string word1, string word2) {  
11:      int i = 0, j = 0, dist = INT_MAX;  
12:      int sz1 = mp[word1].size(), sz2 = mp[word2].size();  
13:      while (i < sz1 && j < sz2) {  
14:        dist = min(dist, abs(mp[word1][i]-mp[word2][j]));  
15:        mp[word1][i] < mp[word2][j] ? i++ : j++;  
16:      }  
17:      return dist;  
18:    }  
19:  };  
20:  // Your WordDistance object will be instantiated and called as such:  
21:  // WordDistance wordDistance(words);  
22:  // wordDistance.shortest("word1", "word2");  
23:  // wordDistance.shortest("anotherWord1", "anotherWord2");  

325. Maximum Size Subarray Sum Equals k

When I saw this problem, my first impression is that it is similar to maximum subarray sum which can be solved by Kadane's algorithm. But this problem requires sum to be k. So, if we have sum[i] to be the sum from [0, i], the problem becomes to find all pairs of sum[i] == k or sum[i]-sum[j] == k. For sum[i] == k, the len is i+1, for sum[i]-sum[j] == k, the length is j - i. If we can save all sums before i in a hash table whose (key, value) pair is (sum, index), to get j which sum[i]-sum[j] == k, we only need to look up the hash table to see if sum[i]-k exists in it.

Note, since we scan from 0 to n, if sum[i] == k, the max length so far must be i+1. Also to avoid duplicates, we only save (sum, i) when this pair isn't existing in hash table. Why we don't have to save the pair (sum, j) later? Because we want to get the maximum size, the first pair guarantees it.

1:  class Solution {  
2:  public:  
3:    int maxSubArrayLen(vector<int>& nums, int k) {  
4:      unordered_map<int, int> mp;  
5:      int sum = 0, maxLen = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        sum += nums[i];  
8:        if (k == sum) maxLen = i+1;  
9:        else if (mp.find(sum-k) != mp.end()) maxLen = max(maxLen, i-mp[sum-k]);  
10:        if (mp.find(sum) == mp.end()) mp[sum] = i;  
11:      }  
12:      return maxLen;  
13:    }  
14:  };  

366. Find Leaves of Binary Tree

I used hash map and DFS to solve this problem. Hash map is used to tag visited node. So the leaf becomes:
1. node->left == NULL && node->left == RIGHT
2. node->left == NULL && mp[node->right] = true
3. node->right == NULL && mp[node->left] = true
4. mp[node->left] == true && mp[node->right] == true

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  private:  
12:    unordered_map<TreeNode*, bool> mp;  
13:  public:  
14:    vector<vector<int>> findLeaves(TreeNode* root) {  
15:      vector<vector<int>> res;  
16:      if (root == NULL) return res;  
17:      while (!mp[root]) {  
18:        vector<int> leaves;  
19:        helper(root, leaves, res);  
20:        res.push_back(leaves);  
21:      }  
22:      return res;  
23:    }  
24:    void helper(TreeNode *root, vector<int> &leaves, vector<vector<int>> &res) {  
25:      if (root->left == NULL && root->right == NULL || mp[root->left] && mp[root->right] ||  
26:        root->left == NULL && mp[root->right] || mp[root->left] && root->right == NULL) {  
27:        leaves.push_back(root->val);  
28:        mp[root] = true;  
29:        return;  
30:      }  
31:      if (root->left && !mp[root->left]) helper(root->left, leaves, res);  
32:      if (root->right && !mp[root->right]) helper(root->right, leaves, res);  
33:      return;  
34:    }  
35:  };  

There is another concise way to solve this problem. We can basically save the node by levels if we know the level.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<vector<int>> findLeaves(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      dfs(root, res);  
15:      return res;  
16:    }  
17:    int dfs(TreeNode* root, vector<vector<int>> &res) {  
18:      if (root == NULL) return 0;  
19:      int level = max(dfs(root->left, res), dfs(root->right, res)) + 1;  
20:      if (level > res.size()) res.push_back(vector<int>());  
21:      res[level-1].push_back(root->val);  
22:      return level;  
23:    }  
24:  };  

379. Design Phone Directory

I was thinking to build up a hash table for every number in the construction function. However, it turns out too costly. Actually, I only needs to have two arrays, with one storing numbers and another storing used tag. The idea behind is that we really don't have to care about the order of number that we dispensed and even who got the number. So don't think over too much. It's a very simple design.

1:  class PhoneDirectory {  
2:  private:  
3:    vector<int> numbers;  
4:    vector<bool> used;  
5:    int front;  
6:    int maxNumbers;  
7:  public:  
8:    /** Initialize your data structure here  
9:      @param maxNumbers - The maximum numbers that can be stored in the phone directory. */  
10:    PhoneDirectory(int maxNumbers) {  
11:      this->maxNumbers = maxNumbers;  
12:      numbers = vector<int>(maxNumbers, 0);  
13:      used = vector<bool>(maxNumbers, false);  
14:      front = 0;  
15:      for (int i = 0; i < maxNumbers; i++) {  
16:        numbers[i] = i;  
17:      }  
18:    }  
19:    /** Provide a number which is not assigned to anyone.  
20:      @return - Return an available number. Return -1 if none is available. */  
21:    int get() {  
22:      if (front == maxNumbers) return -1;  
23:      int ret = numbers[front++];  
24:      used[ret] = true;  
25:      return ret;  
26:    }  
27:    /** Check if a number is available or not. */  
28:    bool check(int number) {  
29:      if (number < 0 || number > maxNumbers-1) return false;  
30:      return !used[number];  
31:    }  
32:    /** Recycle or release a number. */  
33:    void release(int number) {  
34:      if (number >= 0 && number < maxNumbers && used[number]) {  
35:        numbers[--front] = number;  
36:        used[number] = false;  
37:      }  
38:    }  
39:  };  
40:  /**  
41:   * Your PhoneDirectory object will be instantiated and called as such:  
42:   * PhoneDirectory obj = new PhoneDirectory(maxNumbers);  
43:   * int param_1 = obj.get();  
44:   * bool param_2 = obj.check(number);  
45:   * obj.release(number);  
46:   */  

266. Palindrome Permutation

I was thinking to traverse the buckets twice. First round is to count the number of each character. The second round is to count the number of odds. If odds is less than 2, return true. Otherwise, return false.
The top rated solution combine the two rounds into one round but actually the same running time.

1:  class Solution {  
2:  public:  
3:    bool canPermutePalindrome(string s) {  
4:      vector<int> chars(256, 0);  
5:      int odd = 0;  
6:      for (char c : s) {  
7:        odd += ++chars[c] & 1 ? 1 : -1;  
8:      }  
9:      return odd < 2;  
10:    }  
11:  };  

49. Group Anagrams

The anagrams share the same pattern if they are sorted. So what I did is to create a hash table where key is the pattern and the value is the anagrams that have the same pattern. So the algorithm becomes obvious that compute the pattern for each anagram and save it into the hash table.

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> groupAnagrams(vector<string>& strs) {  
4:      unordered_map<string, vector<string>> mp;  
5:      for (int i = 0; i < strs.size(); i++) {  
6:        string key = strs[i];  
7:        sort(key.begin(), key.end());  
8:        mp[key].push_back(strs[i]);  
9:      }  
10:      vector<vector<string>> res;  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        res.push_back(it->second);  
13:      }  
14:      return res;  
15:    }  
16:  };  

Note I use library sort here which I believe takes O(nlogn) time. Since the anagrams here consist of only 26 lower case letters, we can use bucket sort to compute the pattern which reduce the sorting time to O(n).

3. Longest Substring Without Repeating Characters

This is very similar idea to problem "340. Longest Substring with At Most K Distinct Characters".
1. we keep moving one pointer and count each character until one character has been counted before, i.e. the count for the character is one already.
2. Then we move another pointer and decrease the counter for each character until the character pointed by the first pointer has count 0.
3. And then leave the second pointer there and move the first pointer again. Repeat step 1-2 until the first pointer reaches the end.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstring(string s) {  
4:      vector<int> chars(256, 0);  
5:      int i = 0, j = 0, maxLen = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && chars[s[i]] == 0) {++chars[s[i++]];};  
8:        maxLen = max(maxLen, i - j);  
9:        while (i < s.size() && chars[s[i]] == 1) --chars[s[j++]];  
10:      }  
11:      return maxLen;  
12:    }  
13:  };  

138. Copy List with Random Pointer

I used hash map to solve the problem with two rounds.
In first round, copy the list without regard with random pointer but make a map between the old node and new node.
In the second round, fix the random pointer by the hash mapping.

1:  /**  
2:   * Definition for singly-linked list with a random pointer.  
3:   * struct RandomListNode {  
4:   *   int label;  
5:   *   RandomListNode *next, *random;  
6:   *   RandomListNode(int x) : label(x), next(NULL), random(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    RandomListNode *copyRandomList(RandomListNode *head) {  
12:      unordered_map<RandomListNode*, RandomListNode*> mp;  
13:      RandomListNode *dummy = new RandomListNode(-1);  
14:      RandomListNode *cur = head, *res = dummy;  
15:      while (cur) {  
16:        RandomListNode *node = new RandomListNode(cur->label);  
17:        mp[cur] = node;  
18:        res->next = node;  
19:        res = res->next;  
20:        cur = cur->next;  
21:      }  
22:      cur = head;  
23:      res = dummy->next;  
24:      while (cur) {  
25:        if (cur->random != NULL) {  
26:          res->random = mp[cur->random];  
27:        }  
28:        res = res->next;  
29:        cur = cur->next;  
30:      }  
31:      res = dummy->next;  
32:      delete dummy;  
33:      return res;  
34:    }  
35:  };  

1. Two Sum

I was trying to sort the number and find the two sum index by binary search. However, this is completely wrong. Since we need to return the index, we shouldn't sort the array because by doing this the index is changed. So I used hash map to solve the problem.

1:  class Solution {  
2:  public:  
3:    vector<int> twoSum(vector<int>& nums, int target) {  
4:      unordered_map<int, int> hash;  
5:      vector<int> res;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        int t = target - nums[i];  
8:        if (hash.find(t) != hash.end()) {  
9:          res.push_back(i);  
10:          res.push_back(hash[t]);  
11:          break;  
12:        }  
13:        hash[nums[i]] = i;  
14:      }  
15:      return res;  
16:    }  
17:  };  

288. Unique Word Abbreviation

The key idea has bee explained in the code. When I revisited this problem, I made a mistake in line 26. I returned "mp[abbr].size() == 1 && mp[abbr].count(word) == 1". This is wrong because it should be true if the new word does not exist in the hashed set.

1:  class ValidWordAbbr {  
2:  private:  
3:    unordered_map<string, unordered_set<string>> dict;  
4:    bool flag;  
5:    string abbreviation(string word) {  
6:      if (word.size() <= 2) return word;  
7:      return word[0] + to_string(word.size()-2) + word[word.size()-1];  
8:    }  
9:  public:  
10:    ValidWordAbbr(vector<string> &dictionary) {  
11:      for (string s : dictionary) {  
12:        string abbr = abbreviation(s);  
13:        dict[abbr].insert(s);  
14:      }  
15:    }  
16:    bool isUnique(string word) {  
17:      string abbr = abbreviation(word);  
18:      // The idea is set up a hash table whose key is the abbreviation and value is the corresponding word set.  
19:      // We only get true when the word set only contains the input word.  
20:      // Case 1: FALSE, the word set donesn't contain the input word.  
21:      //     e.g. ["dog"]; isUnique("dig"). dict["d1g"].size() = 1 while dict["d1g"].count("dig") = 0.  
22:      // Case 2: TRUE, the word set only contains the input word.  
23:      //     e.g. ["dog"]; isUnique("dog"). dict["d1g"].size() = 1 while dict["d1g"].count("dog") = 1.  
24:      // Case 3: FALSE, the word set contains more than one word.  
25:      //     e.g. ["dog", "dig"]; isUnique("dog"). dict["d1g"].size() = 2 while dict["d1g"].count("dog") = 1.  
26:      return dict[abbr].size() == dict[abbr].count(word);  
27:    }  
28:  };  
29:  // Your ValidWordAbbr object will be instantiated and called as such:  
30:  // ValidWordAbbr vwa(dictionary);  
31:  // vwa.isUnique("hello");  
32:  // vwa.isUnique("anotherWord");  

146. LRU Cache

I made mistake in first place as following. The OJ complains "Runtime Error". After some debugging, I find I did wrong on line 27. When popping out the last element in the list, we need to erase this element in hash map too. However, here comes the question. To erase the element in the hash map, we need to know the key, but in my design, I don't know the key of the last element in the list.

1:  class LRUCache{  
2:  private:  
3:    int cap;  
4:    list<int> l;  
5:    unordered_map<int, list<int>::iterator> mp;  
6:  public:  
7:    LRUCache(int capacity) {  
8:      cap = capacity;  
9:    }  
10:    int get(int key) {  
11:      int ret = -1;  
12:      if (mp.find(key) != mp.end()) {  
13:        ret = *mp[key];  
14:        l.erase(mp[key]);  
15:        l.push_front(ret);  
16:        mp[key] = l.begin();  
17:      }  
18:      return ret;  
19:    }  
20:    void set(int key, int value) {  
21:      if (mp.find(key) != mp.end()) {  
22:        l.erase(mp[key]);  
23:        mp.erase(key);  
24:        l.push_front(value);  
25:        mp[key] = l.begin();  
26:      } else {  
27:        if (l.size() == cap) l.pop_back();  
28:        l.push_front(value);  
29:        mp[key] = l.begin();  
30:      }  
31:    }  
32:  };  

So, the right design should be that the list stores the key and and the value corresponding to the key is wrapped in a pair with the list iterator. And the hash map consists of key and the pair of key and list iterator.

1:  class LRUCache{  
2:  private:  
3:    int cap;  
4:    list<int> l;  
5:    unordered_map<int, pair<int, list<int>::iterator>> mp;  
6:  public:  
7:    LRUCache(int capacity) {  
8:      cap = capacity;  
9:    }  
10:    int get(int key) {  
11:      int ret = -1;  
12:      if (mp.find(key) != mp.end()) {  
13:        ret = mp[key].first;  
14:        l.erase(mp[key].second);  
15:        l.push_front(key);  
16:        mp[key].second = l.begin();  
17:      }  
18:      return ret;  
19:    }  
20:    void set(int key, int value) {  
21:      if (mp.find(key) != mp.end()) {  
22:        l.erase(mp[key].second);  
23:        mp.erase(key);  
24:      } else {  
25:        if (l.size() == cap) {  
26:          mp.erase(l.back());  
27:          l.pop_back();  
28:        }  
29:      }  
30:      l.push_front(key);  
31:      mp[key] = make_pair(value, l.begin());  
32:    }  
33:  };  

359. Logger Rate Limiter

I was trying to solve it as the same way as "362. Design Hit Counter" did. However, after reading the top rated solutions, I realized this problem is much easier. We can have a hash table whose key is the message and value is the expiration time. Once a new message comes in, we check if the timestamp falls in the expiration time which means the existing message is still valid, i.e. it has been printed in last 10 seconds. In this case, we print false. Otherwise, we update the expiration time.

1:  class Logger {  
2:    unordered_map<string, int> mp;  
3:  public:  
4:    /** Initialize your data structure here. */  
5:    Logger() {  
6:    }  
7:    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.  
8:      If this method returns false, the message will not be printed.  
9:      The timestamp is in seconds granularity. */  
10:    bool shouldPrintMessage(int timestamp, string message) {  
11:      if (timestamp < mp[message]) return false;  
12:      mp[message] = timestamp + 10;  
13:      return true;  
14:    }  
15:  };  
16:  /**  
17:   * Your Logger object will be instantiated and called as such:  
18:   * Logger obj = new Logger();  
19:   * bool param_1 = obj.shouldPrintMessage(timestamp,message);  
20:   */  

314. Binary Tree Vertical Order Traversal

This is a level order traversal problem. The trick here we need to track index for each node. If root index is i, then left child index is i-1 and right child index is i. Since the output is from left to right, i.e. from smallest index to largest index, we can use map which has sorted the keys. The index is key and the node vector that has this index as value. So the problem becomes level order traversal nodes, compute index for the node and its children, and push the node to right vector mapped by its index.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<vector<int>> verticalOrder(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      if (!root) return res;  
15:      map<int, vector<int>> mp;  
16:      queue<pair<int, TreeNode *>> q;  
17:      q.push(make_pair(0, root));  
18:      while (!q.empty()) {  
19:        int sz = q.size();  
20:        for (int i = 0; i < sz; i++) {  
21:          pair<int, TreeNode*> node = q.front();  
22:          q.pop();  
23:          int index = node.first;  
24:          mp[index].push_back(node.second->val);  
25:          if (node.second->left) {  
26:            q.push(make_pair(index-1, node.second->left));  
27:          }  
28:          if (node.second->right) {  
29:            q.push(make_pair(index+1, node.second->right));  
30:          }  
31:        }  
32:      }  
33:      for (auto it : mp) {  
34:        res.push_back(it.second);  
35:      }  
36:      return res;  
37:    }  
38:  };  

356. Line Reflection

I followed the hit and solved the problem by set.

1:  class Solution {  
2:  public:  
3:    bool isReflected(vector<pair<int, int>>& points) {  
4:      set<pair<int,int>> s;  
5:      int minX = INT_MAX, maxX = INT_MIN;  
6:      for (int i = 0; i < points.size(); i++) {  
7:        minX = min(points[i].first, minX);  
8:        maxX = max(points[i].first, maxX);  
9:        s.insert(points[i]);  
10:      }  
11:      double y = (minX + maxX) * 1.0 / 2;  
12:      for (int i = 0; i < points.size(); i++) {  
13:        if (!s.count(make_pair(2*y-points[i].first, points[i].second))) return false;  
14:      }  
15:      return true;  
16:    }  
17:  };  

Obviously, this code can be improved because for line 12 we don't have to traverse all points. We can use unordered_map and y as key and the set of its corresponding x's as value. For each y, we traverse from two ends of the set (note numbers in set is sorted). This solution is faster than the first one.

1:  class Solution {  
2:  public:  
3:    bool isReflected(vector<pair<int, int>>& points) {  
4:      unordered_map<int, set<int>> mp;  
5:      int minX = INT_MAX, maxX = INT_MIN;  
6:      for (int i = 0; i < points.size(); i++) {  
7:        minX = min(points[i].first, minX);  
8:        maxX = max(points[i].first, maxX);  
9:        mp[points[i].second].insert(points[i].first);  
10:      }  
11:      double y = (minX + maxX) * 1.0 / 2;  
12:      for (auto i : mp) {  
13:        set<int> tmp = i.second;  
14:        for (auto start = tmp.begin(), end = tmp.end(); start != end; start++) {  
15:          if ((*start + *--end) / 2.0 != y) return false;  
16:          if (start == end) break;  
17:        }  
18:      }  
19:      return true;  
20:    }  
21:  };  

353. Design Snake Game

After visiting the top rated solutions, I know all we need to do is to maintain a double linked queue. Every move, we get the front node's row index and column index. Then we compute the new front's row and column index. And we also need to pop out the tail node. If the new front node is valid, i.e. it is in the board and also it doesn't hit the snake. Then the question is how to know if it hits the snake? This can be done by hash set. The hash set caches all the nodes' positions. As long as the new node can be found in the hash set, we know it hits the snake itself. Since we have a hash set to keep all the nodes' position, whenever we remove/insert a new node from/into the queue, we need to erase/insert it from/into the hash set too. Note, we need to remove the tail BEFORE checking otherwise the snake is one longer than it should be. If the new node is valid, we push the new node to the front and insert it into hash set. And then we check if the new node hits a food. If so, we increment the score and we push the tail back to the queue back.

When I revisited this problem, I missed line 35. It's important to check the index before accessing an array.

1:  class SnakeGame {  
2:  private:  
3:    int w, h, i;  
4:    deque<pair<int, int>> q;  
5:    vector<pair<int, int>> f;  
6:    set<pair<int, int>> s;  
7:  public:  
8:    /** Initialize your data structure here.  
9:      @param width - screen width  
10:      @param height - screen height   
11:      @param food - A list of food positions  
12:      E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */  
13:    SnakeGame(int width, int height, vector<pair<int, int>> food) {  
14:      w = width, h = height, i = 0;  
15:      f = food;  
16:      q.push_back(make_pair(0, 0));  
17:    }  
18:    /** Moves the snake.  
19:      @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down   
20:      @return The game's score after the move. Return -1 if game over.   
21:      Game over when snake crosses the screen boundary or bites its body. */  
22:    int move(string direction) {  
23:      pair<int, int> head = q.front();  
24:      pair<int, int> tail = q.back();  
25:      int r = head.first, c = head.second;  
26:      q.pop_back();  
27:      s.erase(tail);  
28:      if (direction == "U") r--;  
29:      else if (direction == "D") r++;  
30:      else if (direction == "R") c++;  
31:      else if (direction == "L") c--;  
32:      if (r < 0 || r == h || c < 0 || c == w || s.count(make_pair(r, c))) return -1;  
33:      q.push_front(make_pair(r, c));  
34:      s.insert(make_pair(r, c));  
35:      if (i == f.size()) return q.size()-1;  
36:      if (f[i].first == r && f[i].second == c) {  
37:        q.push_back(tail);  
38:        s.insert(make_pair(tail.first, tail.second));  
39:        i++;  
40:      }  
41:      return q.size()-1;  
42:    }  
43:  };  
44:  /**  
45:   * Your SnakeGame object will be instantiated and called as such:  
46:   * SnakeGame obj = new SnakeGame(width, height, food);  
47:   * int param_1 = obj.move(direction);  
48:   */  

358. Rearrange String k Distance Apart

This is similar idea to the count sort. First of all, we use hash table to mapping the letter and their appearance times in the input string. And then we want to reorder the string by place k different letters in a row. How can we achieve that? We want to place the letter that has most appearance first. Why? If you place the least appearance first, then you'll be ending up having most appearance letters only and not being able to make k different letters in a row early on. So we think of maximum heap for help. The maximum heap honors the appearance time. Once we place a letter, we need to remove the letter from the heap because it could be still the letter with most appearance but we can't place it until we've place k letters. On the other hand, we still need to cache the removed letters if they still have one more appearance. Once we finish placing k different letters, we push the cached letters back to the heap. Now, the question is in what situation we can't rearrange the string? When we are rearranging k letters, as long as the heap has more than k letters we are find. However, if the heap becomes empty (note we are removing letters when we've placed them), it means we can't make k different letters in a row. At this moment, we know that this string can't be rearranged.

1:  class Solution {  
2:  public:  
3:    string rearrangeString(string str, int k) {  
4:      if (k == 0) return str;  
5:      int l = str.size();  
6:      string res;  
7:      unordered_map<char, int> mp;  
8:      priority_queue<pair<int, char>> pq;  
9:      for (int i = 0; i < l; i++) mp[str[i]]++;  
10:      for (auto it : mp) pq.push(make_pair(it.second, it.first));  
11:      while (!pq.empty()) {  
12:        vector<pair<int, char>> cache;  
13:        int c = min(l, k);  
14:        for (int i = 0; i < c; i++) {  
15:          if (pq.empty()) return "";  
16:          pair<int, char> tmp = pq.top();  
17:          pq.pop();  
18:          res += tmp.second;  
19:          if (--tmp.first > 0) cache.push_back(tmp);  
20:          l--;  
21:        }  
22:        for (auto i : cache) pq.push(i);  
23:      }  
24:      return res;  
25:    }  
26:  };  

249. Group Shifted Strings

The intuition is to create a pattern for each string and use the pattern as key in hash table. The value is a string vector that contains all strings follow the same pattern. Then the problem becomes how to create the pattern. The naive way is to use "a" + diff. Since the diff can be negative (e.g. "ba" and "az"), we should 26 to it.

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> groupStrings(vector<string>& strings) {  
4:      unordered_map<string, vector<string>> mp;  
5:      for (string s : strings) {  
6:        mp[pattern(s)].push_back(s);  
7:      }  
8:      vector<vector<string>> res;  
9:      for (auto it : mp) {  
10:        vector<string> r = it.second;  
11:        sort(r.begin(), r.end());  
12:        res.push_back(r);  
13:      }  
14:      return res;  
15:    }  
16:    string pattern(string &s) {  
17:      string p = "";  
18:      for (int i = 1; i < s.size(); i++) {  
19:        int diff = s[i]-s[i-1];  
20:        if (diff < 0) diff += 26;  
21:        p += "a" + to_string(diff);  
22:      }  
23:      return p;  
24:    }  
25:  };  

246. Strobogrammatic Number

I did naive way first.

1:  class Solution {  
2:  public:  
3:    bool isStrobogrammatic(string num) {  
4:      if (num.size() == 0) return true;  
5:      int l = 0, r = num.size()-1;  
6:      while (l < r) {  
7:        if ((num[l] == '6' && num[r] == '9') || (num[l] == '9' && num[r] == '6') ||  
8:           (num[l] == num[r] && num[l] == '1') || (num[l] == num[r] && num[l] == '8' ||  
9:           (num[l] == num[r] && num[l] == '0'))) {  
10:          l++; r--;     
11:        } else {  
12:          return false;  
13:        }  
14:      }  
15:      if (num.size() & 1) return num[l] == '8' || num[l] == '1' || num[l] == '0';  
16:      return true;  
17:    }  
18:  };  

Then I read the top rated solution and realized that we can set up a look up table first and the code becomes very concise.

1:  class Solution {  
2:  public:  
3:    bool isStrobogrammatic(string num) {  
4:      unordered_map<char, char> dict{{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};  
5:      int n = num.length();  
6:      for (int l = 0, r = n - 1; l <= r; l++, r--)  
7:        if (dict.find(num[l]) == dict.end() || dict[num[l]] != num[r])  
8:          return false;   
9:      return true;   
10:    }  
11:  };