diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/word_search2.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/word_search2.cpp')
-rw-r--r-- | other/word_search2.cpp | 70 |
1 files changed, 70 insertions, 0 deletions
diff --git a/other/word_search2.cpp b/other/word_search2.cpp new file mode 100644 index 0000000..8163966 --- /dev/null +++ b/other/word_search2.cpp @@ -0,0 +1,70 @@ +#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; +} |