336. Palindrome Pairs

I tried brute force solution first, i.e. check if a new concatenated word is constructed before and if so we continue otherwise we need to check the new word and insert it into the hash table if it is a valid palindrome. This way runs O(n*n) time and can't pass large test set.

The one of top rated solution does a trick, i.e. it uses the reserve of word as the hash map key and the word's index as value. And the idea is for each word, scan from left to right, if left partition can be found in the hash map and the right partition is palindrome, then we'll find a palindrome, i.e.  "left partition | right partition | dict candidate". On the other hand, if right partition is found, then we find "candidate | left partition | right partition | ". There are some edge cases that need attention. I've added some comments in the code for the edge cases.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> palindromePairs(vector<string>& words) {  
4:      unordered_map<string, int> dict;  
5:      vector<vector<int>> res;  
6:      for (int i = 0; i < words.size(); i++) {  
7:        string key = words[i];  
8:        reverse(key.begin(), key.end());  
9:        dict[key] = i;  
10:      }  
11:      for (int i = 0; i < words.size(); i++) {  
12:        for (int j = 0; j < words[i].size(); j++) {  
13:          string left = words[i].substr(0, j);  
14:          // words[i].size()-j > 0, which means this logic doesn't cover the case  
15:          // where right is empty, i.e. ""  
16:          string right = words[i].substr(j, words[i].size()-j);  
17:          // we need to kick out the case where words[i] itself is a palindrome  
18:          if (dict.find(left) != dict.end() && isPalindrome(right) && dict[left] != i) {  
19:            res.push_back({i, dict[left]});  
20:          }  
21:          if (dict.find(right) != dict.end() && isPalindrome(left) && dict[right] != i) {  
22:            res.push_back({dict[right], i});  
23:          }  
24:        }  
25:      }  
26:      // process the missing case above.  
27:      if (dict.find("") != dict.end()) {  
28:        for (int i = 0; i < words.size(); i++) {  
29:          if (isPalindrome(words[i]) && dict[""] != i) res.push_back({dict[""], i});  
30:        }  
31:      }  
32:      return res;  
33:    }  
34:    bool isPalindrome(string s) {  
35:      int l = 0, r = s.size()-1;  
36:      while (l < r) {  
37:        if (s[l++] != s[r--]) return false;  
38:      }  
39:      return true;  
40:    }  
41:  };  

Note, this problem involves searching word, then what data structure you can think of that is much faster than hash table? Yes, it is Trie. We can build trie tree for each reversed word just like what we did above inserting reversed word into hash map. And then we can follow the same idea to solve this problem.

212. Word Search II

My initial idea is to use dfs for each character in the board. And for each dfs, we search the word so far in the dictionary. The dictionary is a hash table built by the input vector words. However, by the idea of trie, it'll be much faster than hash table. Note, to avoid duplicates, I use the set instead of array to hold the results.

1:  class TrieNode {  
2:  public:  
3:    TrieNode *next[26];  
4:    bool isEnd;  
5:    TrieNode() {  
6:      memset(next, 0, sizeof(next));  
7:      isEnd = false;  
8:    }  
9:  };  
10:  class Trie {  
11:  public:  
12:    TrieNode *next[26];  
13:    bool isEnd;  
14:    Trie (vector<string> &words) {  
15:      root = new TrieNode();  
16:      for (int i = 0; i < words.size(); i++) {  
17:        _insert(words[i]);  
18:      }  
19:    }  
20:    TrieNode *getRoot() {  
21:      return root;  
22:    }  
23:  private:  
24:    TrieNode *root;  
25:    void _insert(string word) {  
26:      TrieNode *p = root;  
27:      for (int i = 0; i < word.size(); i++) {  
28:        if (p->next[word[i]-'a'] == NULL) {  
29:          p->next[word[i]-'a'] = new TrieNode();  
30:        }  
31:        p = p->next[word[i]-'a'];  
32:      }  
33:      p->isEnd = true;  
34:    }  
35:  };  
36:  class Solution {  
37:  public:  
38:    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {  
39:      Trie *trie = new Trie(words);  
40:      TrieNode *root = trie->getRoot();  
41:      unordered_set<string> res;  
42:      string sol;  
43:      for (int i = 0; i < board.size(); i++) {  
44:        for (int j = 0; j < board[0].size(); j++) {  
45:          find(board, i, j, root, sol, res);  
46:        }  
47:      }  
48:      return vector<string>(res.begin(), res.end());;  
49:    }  
50:    void find(vector<vector<char>> &board, int i, int j, TrieNode *t, string sol, unordered_set<string> &res) {  
51:      if (i < 0 || j < 0 || i == board.size() || j == board[0].size() || board[i][j] == 0) return;  
52:      if (t->next[board[i][j]-'a'] != NULL) {  
53:        sol += board[i][j];  
54:        t = t->next[board[i][j]-'a'];  
55:        if (t->isEnd) res.insert(sol);  
56:        char c = board[i][j];  
57:        board[i][j] = 0;  
58:        find(board, i+1, j, t, sol, res);  
59:        find(board, i-1, j, t, sol, res);  
60:        find(board, i, j+1, t, sol, res);  
61:        find(board, i, j-1, t, sol, res);  
62:        board[i][j] = c;  
63:      }  
64:    }  
65:  };  

When I revisited this problem, I had following solution which has the same idea. I made mistakes in,
line 20: I put this line into the if clause which misses the case when the next trie node isn't null.
line 54: I was using vector first but it will include some duplicates. So I changed it to set.
line 56-58: First of all, I had line 58 before line 56-57. This results in empty output. Then, I realized that line 58 should check after we've include the new trie node (because the root in dfs() function is the parent node trie node). However, the result missed last node in a word. Then I eventually moved line 58 behind line 56-57 and get the correct result.

Also it is very easy to make mistake in line 65 to pass "root->next[board[i][j]-'a']" to the dfs function. Note at that moment, board[i][j] has been changed to 0 so you'll get segment fault.

1:  class TrieNode {  
2:  public:  
3:    bool isEnd;  
4:    vector<TrieNode *> next;  
5:    TrieNode() {  
6:      isEnd = false;  
7:      next = vector<TrieNode *>(26, NULL);  
8:    }  
9:  };  
10:  class Trie {  
11:  private:  
12:    TrieNode *root;  
13:    void _insert(string word) {  
14:      TrieNode *p = root;  
15:      for (int i = 0; i < word.size(); i++) {  
16:        int index = word[i]-'a';  
17:        if (p->next[index] == NULL) {  
18:          p->next[index] = new TrieNode();  
19:        }  
20:        p = p->next[index];  
21:      }  
22:      p->isEnd = true;  
23:    }  
24:  public:  
25:    Trie(vector<string> &words) {  
26:      root = new TrieNode();  
27:      for (int i = 0; i <words.size(); i++) {  
28:        _insert(words[i]);  
29:      }  
30:    }  
31:    TrieNode *getRoot() {  
32:      return root;  
33:    }  
34:  };  
35:  class Solution {  
36:  private:  
37:    int row, col;  
38:    vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  
39:  public:  
40:    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {  
41:      set<string> res;  
42:      row = board.size();  
43:      if (row == 0) return vector<string>();  
44:      col = board[0].size();  
45:      Trie *trie = new Trie(words);  
46:      TrieNode *root = trie->getRoot();  
47:      for (int i = 0; i < row; i++) {  
48:        for (int j = 0; j < col; j++) {  
49:          dfs(board, i, j, root, "", res);  
50:        }  
51:      }  
52:      return vector<string>(res.begin(), res.end());  
53:    }  
54:    void dfs(vector<vector<char>> &board, int i, int j, TrieNode *root, string path, set<string> &res) {  
55:      if (root->next[board[i][j]-'a'] == NULL) return;  
56:      root = root->next[board[i][j]-'a'];  
57:      path += board[i][j];  
58:      if (root->isEnd) res.insert(path);  
59:      char c = board[i][j];  
60:      board[i][j] = 0;  
61:      for (int d = 0; d < dir.size(); d++) {  
62:        int ii = i + dir[d].first;  
63:        int jj = j + dir[d].second;  
64:        if (ii < 0 || ii == row || jj < 0 || jj == col || board[ii][jj] == 0) continue;  
65:        dfs(board, ii, jj, root, path, res);  
66:      }  
67:      board[i][j] = c;  
68:    }  
69:  };  

208. Implement Trie (Prefix Tree)

There is a very good video explaining what tries is though the implementation is Java.
https://www.youtube.com/watch?v=EjD5PJJoeLU

I followed the way video does to implement trie. I made a mistake in first place to initialize the TrieNode* array. I used 26 instead of sizeof(next). The third argument for memset actually should be computed as 26*sizeof(TrieNode*). Otherwise, you'll get run time error because of accessing invalid memory.

1:  class TrieNode {  
2:  public:  
3:    TrieNode *next[26];  
4:    bool isEnd;  
5:    // Initialize your data structure here.  
6:    TrieNode(bool b = false) {  
7:      memset(next, 0, sizeof(next));  
8:      isEnd = b;  
9:    }  
10:  };  
11:  class Trie {  
12:  public:  
13:    Trie() {  
14:      root = new TrieNode();  
15:    }  
16:    // Inserts a word into the trie.  
17:    void insert(string word) {  
18:      _insert(root, word, 0);  
19:    }  
20:    // Returns if the word is in the trie.  
21:    bool search(string word) {  
22:      return _search(root, word, 0);  
23:    }  
24:    // Returns if there is any word in the trie  
25:    // that starts with the given prefix.  
26:    bool startsWith(string prefix) {  
27:      return _startsWith(root, prefix, 0);  
28:    }  
29:  private:  
30:    TrieNode* root;  
31:    void _insert(TrieNode *node, string &word, int i) {  
32:      if (i == word.size()) {  
33:        node->isEnd = true;  
34:        return;  
35:      }  
36:      int j = word[i]-'a';  
37:      if (node->next[j] == NULL) node->next[j] = new TrieNode();  
38:      _insert(node->next[j], word, i+1);  
39:    }  
40:    bool _search(TrieNode *node, string &word, int i) {  
41:      if (i == word.size()) return node->isEnd;  
42:      int j = word[i]-'a';  
43:      if (node->next[j] == NULL) return false;  
44:      return _search(node->next[j], word, i+1);  
45:    }  
46:    bool _startsWith(TrieNode *node, string &prefix, int i) {  
47:      if (i == prefix.size()) return true;  
48:      int j = prefix[i]-'a';  
49:      if (node->next[j] == NULL) return false;  
50:      return _startsWith(node->next[j], prefix, i+1);  
51:    }  
52:  };  

Also, there is iterative way to implement it.

1:  #define R 26  
2:  class TrieNode {  
3:  public:  
4:    TrieNode *next[R];  
5:    bool isEnd;  
6:    // Initialize your data structure here.  
7:    TrieNode() {  
8:      memset(next, 0, R*sizeof(TrieNode*));  
9:      isEnd = false;  
10:    }  
11:  };  
12:  class Trie {  
13:  public:  
14:    Trie() {  
15:      root = new TrieNode();  
16:    }  
17:    // Inserts a word into the trie.  
18:    void insert(string word) {  
19:      TrieNode *p = root;  
20:      for (int i = 0; i < word.size(); i++) {  
21:        if (p->next[word[i]-'a'] == NULL) {  
22:          p->next[word[i]-'a'] = new TrieNode();  
23:        }  
24:        p = p->next[word[i]-'a'];  
25:      }  
26:      p->isEnd = true;  
27:    }  
28:    // Returns if the word is in the trie.  
29:    bool search(string word) {  
30:      TrieNode *p = find(word);  
31:      return p && p->isEnd;  
32:    }  
33:    // Returns if there is any word in the trie  
34:    // that starts with the given prefix.  
35:    bool startsWith(string prefix) {  
36:      return find(prefix) != NULL;  
37:    }  
38:  private:  
39:    TrieNode* root;  
40:    TrieNode *find(string word) {  
41:      TrieNode *p = root;  
42:      for (int i = 0; i < word.size() && p; i++) {  
43:        p = p->next[word[i]-'a'];  
44:      }  
45:      return p;  
46:    }  
47:  };  
48:  // Your Trie object will be instantiated and called as such:  
49:  // Trie trie;  
50:  // trie.insert("somestring");  
51:  // trie.search("key");*/