A simple combination of Implement Trie (Prefix Tree) and Word Search. If you've solved them, this problem will become easy :-)
The following code is based on DFS and should be self-explanatory enough. Well, just go ahead and read it. It is long but clear :-)
1 class TrieNode { 2 public: 3 bool isKey; 4 TrieNode* children[26]; 5 TrieNode() : isKey(false) { 6 memset(children, NULL, sizeof(TrieNode*) * 26); 7 } 8 }; 9 10 class Trie { 11 public: 12 Trie() { 13 root = new TrieNode(); 14 } 15 16 void add(string& word) { 17 TrieNode* run = root; 18 for (char c : word) { 19 if (!(run -> children[c - 'a'])) 20 run -> children[c - 'a'] = new TrieNode(); 21 run = run -> children[c - 'a']; 22 } 23 run -> isKey = true; 24 } 25 26 bool search(string& word) { 27 TrieNode* p = query(word); 28 return p && p -> isKey; 29 } 30 31 bool startsWith(string& prefix) { 32 return query(prefix) != NULL; 33 } 34 private: 35 TrieNode* root; 36 TrieNode* query(string& s) { 37 TrieNode* run = root; 38 for (char c : s) { 39 if (!(run -> children[c - 'a'])) return NULL; 40 run = run -> children[c - 'a']; 41 } 42 return run; 43 } 44 }; 45 46 class Solution { 47 public: 48 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { 49 Trie trie = Trie(); 50 for (string word : words) trie.add(word); 51 int m = board.size(), n = board[0].size(); 52 for (int r = 0; r < m; r++) 53 for (int c = 0; c < n; c++) 54 find(trie, board, "", r, c); 55 return vector<string> (st.begin(), st.end()); 56 } 57 private: 58 unordered_set<string> st; 59 void find(Trie trie, vector<vector<char>>& board, string word, int r, int c) { 60 int m = board.size(), n = board[0].size(); 61 if (board[r][c] == '%') return; 62 word += board[r][c]; 63 if (!trie.startsWith(word)) return; 64 if (trie.search(word)) st.insert(word); 65 board[r][c] = '%'; 66 if (r) find(trie, board, word, r - 1, c); 67 if (r < m - 1) find(trie, board, word, r + 1, c); 68 if (c) find(trie, board, word, r, c - 1); 69 if (c < n - 1) find(trie, board, word, r, c + 1); 70 board[r][c] = word.back(); 71 } 72 };
