aboutsummaryrefslogtreecommitdiff
path: root/word_search2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'word_search2.cpp')
-rw-r--r--word_search2.cpp70
1 files changed, 0 insertions, 70 deletions
diff --git a/word_search2.cpp b/word_search2.cpp
deleted file mode 100644
index 8163966..0000000
--- a/word_search2.cpp
+++ /dev/null
@@ -1,70 +0,0 @@
-#include "leetcode.h"
-
-struct Trie {
- bool isEnd;
- string word;
- Trie *child[26];
- Trie() {
- isEnd = false;
- word = "";
- for (int i = 0; i < 26; i++)
- child[i] = NULL;
- }
-};
-
-class Solution {
-public:
- vector<string> ans;
- vector<string> findWords(vvd(char) & board, vector<string> &words) {
- int n = board.size(), m = board[0].size();
- for (auto w : words)
- insert(w);
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- dfs(board, i, j, n, m, root);
- return ans;
- }
-
-private:
- vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
- Trie *root = new Trie();
- void insert(string &s) {
- int n = s.size();
- Trie *curr = root;
- for (int i = 0; i < n; i++) {
- int idx = s[i] - 'a';
- if (curr->child[idx] == NULL)
- curr->child[idx] = new Trie();
- curr = curr->child[idx];
- }
- curr->isEnd = true;
- curr->word = s;
- }
- void dfs(vvd(char) & board, int i, int j, int n, int m, Trie *curr) {
- if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] == '#')
- return;
- int idx = board[i][j] - 'a';
- if (curr->child[idx] == NULL)
- return;
- curr = curr->child[idx];
- if (curr->isEnd) {
- ans.push_back(curr->word);
- curr->isEnd = false;
- }
- char val = board[i][j];
- board[i][j] = '#';
- for (int k = 0; k < 4; k++) {
- int newI = i + dx[k], newJ = j + dy[k];
- dfs(board, newI, newJ, n, m, curr);
- }
- board[i][j] = val;
- }
-};
-
-int main() {
- Solution obj;
- vvd(char) board = {{'a', 'b'}, {'c', 'd'}};
- vector<string> words = {"abcb"};
- for (auto i : obj.findWords(board, words))
- cout << i << endl;
-}