From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/word_search2.cpp | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) create mode 100644 other/word_search2.cpp (limited to 'other/word_search2.cpp') 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 ans; + vector findWords(vvd(char) & board, vector &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 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 words = {"abcb"}; + for (auto i : obj.findWords(board, words)) + cout << i << endl; +} -- cgit v1.2.3